Rosetta Code

Primality by trial division: Difference between revisions

Page Discussion

Primality by trial division (view source)

Revision as of 19:30, 1 May 2024

6,735 bytes added ,  18 days ago
→‎Functional
(Add Miranda)
 
(21 intermediate revisions by 11 users not shown)
Line 368:
endmethod.
ENDCLASS.</syntaxhighlight>
 
=={{header|ABC}}==
<syntaxhighlight lang="ABC">HOW TO REPORT prime n:
REPORT n>=2 AND NO d IN {2..floor root n} HAS n mod d = 0
 
FOR n IN {1..100}:
IF prime n: WRITE n</syntaxhighlight>
{{out}}
<pre>2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97</pre>
 
=={{header|ACL2}}==
Line 681 ⟶ 690:
{{output}}
<syntaxhighlight lang="applescript">{2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97}</syntaxhighlight>
 
=={{header|ARM Assembly}}==
{{works with|as|Raspberry Pi <br> or android 32 bits with application Termux}}
<syntaxhighlight lang ARM Assembly>
/* ARM assembly Raspberry PI */
/* program testtrialprime.s */
 
/************************************/
/* Constantes */
/************************************/
/* for this file see task include a file in language ARM assembly*/
.include "../constantes.inc"
 
//.include "../../ficmacros32.inc" @ for debugging developper
/************************************/
/* Initialized data */
/************************************/
.data
szMessPrime: .asciz " is prime.\n"
szMessNotPrime: .asciz " is not prime.\n"
szCarriageReturn: .asciz "\n"
szMessStart: .asciz "Program 32 bits start.\n"
/************************************/
/* UnInitialized data */
/************************************/
.bss
sZoneConv: .skip 24
/************************************/
/* code section */
/************************************/
.text
.global main
main: @ entry of program
ldr r0,iAdrszMessStart
bl affichageMess
mov r0,#19
bl testPrime
ldr r0,iStart @ number
bl testPrime
ldr r0,iStart1 @ number
bl testPrime
100: @ standard end of the program
mov r0, #0 @ return code
mov r7, #EXIT @ request to exit program
swi 0 @ perform the system call
iAdrsZoneConv: .int sZoneConv
 
iAdrszMessPrime: .int szMessPrime
iAdrszMessNotPrime: .int szMessNotPrime
iAdrszCarriageReturn: .int szCarriageReturn
iAdrszMessStart: .int szMessStart
iStart: .int 2600002183
iStart1: .int 4124163031
/******************************************************************/
/* test if number is prime */
/******************************************************************/
/* r0 contains the number */
testPrime:
push {r1,r2,lr} @ save registers
mov r2,r0
ldr r1,iAdrsZoneConv
bl conversion10 @ decimal conversion
ldr r0,iAdrsZoneConv
bl affichageMess
mov r0,r2
bl isPrime
cmp r0,#0
beq 1f
ldr r0,iAdrszMessPrime
bl affichageMess
b 100f
1:
ldr r0,iAdrszMessNotPrime
bl affichageMess
100:
pop {r1,r2,pc} @ restaur registers
/******************************************************************/
/* test if number is prime */
/******************************************************************/
/* r0 contains the number */
/* r0 return 1 if prime else return 0 */
isPrime:
push {r4,lr} @ save registers
cmp r0,#1 @ <= 1 ?
movls r0,#0 @ not prime
bls 100f
cmp r0,#3 @ 2 and 3 prime
movls r0,#1
bls 100f
tst r0,#1 @ even ?
moveq r0,#0 @ not prime
beq 100f
mov r4,r0 @ save number
mov r1,#3 @ first divisor
1:
mov r0,r4 @ number
bl division
add r1,r1,#2 @ increment divisor
cmp r3,#0 @ remainder = zero ?
moveq r0,#0 @ not prime
beq 100f
cmp r1,r2 @ divisors<=quotient ?
ble 1b @ loop
mov r0,#1 @ return prime
 
100:
pop {r4,pc} @ restaur registers
/***************************************************/
/* ROUTINES INCLUDE */
/***************************************************/
/* for this file see task include a file in language ARM assembly*/
.include "../affichage.inc"
</syntaxhighlight>
{{Out}}
<pre>
Program 32 bits start.
19 is prime.
2600002183 is prime.
4124163031 is not prime.
</pre>
 
=={{header|Arturo}}==
Line 801 ⟶ 932:
 
=={{header|BASIC}}==
==={{header|Applesoft BASIC}}===
<syntaxhighlight lang="basic"> 100 DEF FN MOD(NUM) = NUM - INT (NUM / DIV) * DIV: REM NUM MOD DIV
110 FOR I = 1 TO 99
120 V = I: GOSUB 200"ISPRIME
130 IF ISPRIME THEN PRINT " "I;
140 NEXT I
150 END
200 ISPRIME = FALSE: IF V < 2 THEN RETURN
210 DIV = 2:ISPRIME = FN MOD(V): IF NOT ISPRIME THEN ISPRIME = V = 2: RETURN
220 LIMIT = SQR (V): IF LIMIT > = 3 THEN FOR DIV = 3 TO LIMIT STEP 2:ISPRIME = FN MOD(V): IF ISPRIME THEN NEXT DIV
230 RETURN</syntaxhighlight>
==={{header|BASIC256}}===
{{trans|FreeBASIC}}
Line 860 ⟶ 1,003:
89 is prime
97 is prime</pre>
 
==={{header|Craft Basic}}===
<syntaxhighlight lang="basic">for i = 1 to 50
 
if i < 2 then
 
let p = 0
 
else
 
if i = 2 then
 
let p = 1
 
else
 
if i % 2 = 0 then
 
let p = 0
 
else
 
let p = 1
 
for j = 3 to int(i ^ .5) step 2
 
if i % j = 0 then
 
let p = 0
break j
 
endif
 
wait
 
next j
 
endif
 
endif
 
endif
 
if p <> 0 then
 
print i
 
endif
 
next i</syntaxhighlight>
{{out| Output}}<pre>2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 </pre>
 
==={{header|FBSL}}===
Line 2,175 ⟶ 2,369:
=={{header|EasyLang}}==
<syntaxhighlight lang="easylang">
func isPrimeisprim num . result$n .
if numn < 2
result$return = "false"0
break 1
.
if numn mod 2 = 0 and numn > 2
result$return = "false"0
break 1
.
for i = 3 to sqrt num
sq = sqrt if num mod i = 0n
while i result$ <= "false"sq
if n mod breaki 2= 0
return 0
.
i += 2
.
result$return = "true"1
.
print isprim 1995937
</syntaxhighlight>
 
Line 2,841 ⟶ 3,036:
 
=={{header|langur}}==
=== Functional ===
{{trans|Raku}}
following the Raku example, which states, "Integer $i is prime if it is greater than one and is divisible by none of 2, 3, up to the square root of $i" (plus an adjustment for the prime number 2)
 
Below, we use an implied parameter (.i) on the .isPrime function.
 
<syntaxhighlight lang="langur">val .isPrime = fn(.i) {
.i == 2 or .i > 2 and
not any fn(.x) { .i div .x }, pseries 2 .. .i ^/ 2
}
 
writeln filter .isPrime, series 100</syntaxhighlight>
 
=== Recursive ===
{{trans|Go}}
<syntaxhighlight lang="langur">val .isPrime = fn(.i) {
{{works with|langur|0.11}}
<syntaxhighlight lang="langur">val .isPrime = f(.i) {
val .n = abs(.i)
if .n <= 2: return .n == 2
 
val .chkdiv = ffn(.n, .i) {
if .i x* .i <= .n {
return .n ndiv .i and self(.n, .i+2)
}
Line 2,857 ⟶ 3,064:
return .n ndiv 2 and .chkdiv(.n, 3)
}
 
writeln filter .isPrime, series 100</syntaxhighlight>
 
=== Functional ===
{{trans|Raku}}
following the Raku example, which states, "Integer $i is prime if it is greater than one and is divisible by none of 2, 3, up to the square root of $i" (plus an adjustment for the prime number 2)
 
Below, we use an implied parameter (.i) on the .isPrime function.
 
{{works with|langur|0.11}}
<syntaxhighlight lang="langur">val .isPrime = f .i == 2 or
.i > 2 and not any f(.x) .i div .x, pseries 2 .. .i ^/ 2
 
writeln filter .isPrime, series 100</syntaxhighlight>
Line 2,936 ⟶ 3,131:
=={{header|M2000 Interpreter}}==
<syntaxhighlight lang="m2000 interpreter">
Module Primality_by_trial_division {
Inventory Known1=2@, 3@
Inventory Known1=2@, 3@
IsPrime=lambda Known1 (x as decimal) -> {
IsPrime=lambda Known1 (x as decimal) -> {
=0=1
=false
if exist(Known1, x) then =1=1 : exit
if exist(Known1, x) then =true : exit
if x<=5 OR frac(x) then {if x == 2 OR x == 3 OR x == 5 then Append Known1, x : =1=1
if x<=5 OR frac(x) then {if x == 2 OR x == 3 OR x == 5 then Append Known1, x : =true
Break}
Break}
if frac(x/2) else exit
if frac(x/32) else exit
if frac(x/3) else exit
x1=sqrt(x):d = 5@
x1=sqrt(x):d = 5@
{if frac(x/d ) else exit
do
d += 2: if d>x1 then Append Known1, x : =1=1 : exit
if frac(x/d) else exit
d += 42: if d<= >x1 elsethen Append Known1, x : =true =1=1: exit
if frac(x/d) else exit
loop}
d += 4: if d<= x1 else Append Known1, x : =true: exit
}
always
}
i=2
While Len(Known1)<20 {
i=2
dummy=Isprime(i)
While Len(Known1)<20
i++
dummy=Isprime(i) }
i++
Print "first ";len(known1);" primes"
End While
Print Known1
Print "Fromfirst 110 to";len(known1);" 130primes"
Print Known1
count=0
Print "From For i=110 to 130 {"
count=0
If isPrime(i) Then Print i, : count++
For i=110 to 130
}
If isPrime(i) Then Print i, : count++
Print
Next
Print "Found ";count;" primes"
Print
Print "Found ";count;" primes"
}
Primality_by_trial_division
</syntaxhighlight>
 
Line 4,059 ⟶ 4,258:
=={{header|Quackery}}==
 
<code>sqrt+</code> is defined at [[Isqrt (integer square root) of X#Quackery]].
 
<syntaxhighlight lang="quackery"> [ dup 4 < iff [ 1 > ] done
dup 1 & not iff [ drop false ] done
true swap dup sqrt+
0 = iff [ 2drop not ] done
1 >> times
Line 4,287 ⟶ 4,486:
|-
|
≪ / LAST ROT * - #0 == ≫ ''''<span style="color:blue">BDIV?'''</span>' STO
≪
'''IF''' DUP #3 ≤ '''THEN''' #2 / B→R
'''ELSE'''
'''IF''' DUP #2 '''<span style="color:blue">BDIV?'''</span> OVER #3 '''BDIV?''' OR
'''THEN''' DROP 0
'''ELSE'''
Line 4,298 ⟶ 4,497:
≪ a #2 #5 1 SF
'''WHILE''' 1 FS? OVER maxd ≤ AND '''REPEAT'''
'''IF''' a OVER '''<span style="color:blue">BDIV?'''</span> '''THEN''' 1 CF '''END'''
OVER + #6 ROT - SWAP '''END'''
≫
SWAP DROP '''<span style="color:blue">BDIV?'''</span> NOT
'''END'''
'''END'''
≫ ''''<span style="color:blue">BPRIM?'''</span>' STO
|
<span style="color:blue">BDIV?</span> ''( #a #b -- boolean )''
<span style="color:blue">BPRIM?</span> ''( #a -- boolean )''
return 1 if a is 2 or 3
Line 4,325 ⟶ 4,524:
|}
'''Floating point version'''
 
Faster but limited to 1E12.
≪ '''IF''' DUP 5 ≤ '''THEN''' { 2 3 5 } SWAP POS
'''ELSE'''
'''IF''' DUP 2 MOD NOT '''THEN''' 2
'''ELSE'''
DUP √ CEIL → lim
≪ 3 '''WHILE''' DUP2 MOD OVER lim ≤ AND '''REPEAT''' 2 + '''END'''
≫
'''END''' MOD
'''END''' SIGN
≫ '<span style="color:blue">PRIM?</span>' STO
 
=={{header|Ruby}}==
Line 4,709 ⟶ 4,921:
Original source: [http://seed7.sourceforge.net/algorith/math.htm#is_prime]
 
=={{header|SETL}}==
<syntaxhighlight lang="setl">program trial_division;
print({n : n in {1..100} | prime n});
 
op prime(n);
return n>=2 and not exists d in {2..floor sqrt n} | n mod d = 0;
end op;
end program;</syntaxhighlight>
{{out}}
<pre>{2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97}</pre>
=={{header|Sidef}}==
<syntaxhighlight lang="ruby">func is_prime(a) {
Line 4,999 ⟶ 5,221:
end
endmodule</syntaxhighlight>
 
=={{header|V (Vlang)}}==
<syntaxhighlight lang="Zig">
import math
 
const numbers = [5, 3, 14, 19, 25, 59, 88]
 
fn main() {
for num in numbers {
println("${num} is a prime number? " + if is_prime(num) == true {'yes'} else {'no'})
}
}
 
fn is_prime(num int) bool {
if num <= 1 {return false}
if num % 2 == 0 && num != 2 {return false}
for idx := 3; idx <= math.floor(num / 2) - 1; idx += 2 {
if num % idx == 0 {return false}
}
return true
}
</syntaxhighlight>
 
{{out}}
<pre>
5 is a prime number? yes
3 is a prime number? yes
14 is a prime number? no
19 is a prime number? yes
25 is a prime number? no
59 is a prime number? yes
88 is a prime number? no
</pre>
 
=={{header|Wren}}==
{{libheader|Wren-fmt}}
<syntaxhighlight lang="ecmascriptwren">import "./fmt" for Fmt
 
var isPrime = Fn.new { |n|
Line 5,018 ⟶ 5,273:
System.print("Are the following prime?")
for (test in tests) {
SystemFmt.print("%(Fmt.d(2$2d -> $y", test)), -> %(isPrime.call(test) ? "yes" : "no")")
}</syntaxhighlight>
 
Langurmonkey
885

edits

Retrieved from "https://rosettacode.org/wiki/Special:MobileDiff/338756...364151"