Primality by trial division: Difference between revisions
→Functional
Not a robot (talk | contribs) (Add MAD) |
Langurmonkey (talk | contribs) |
||
| (36 intermediate revisions by 13 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 634 ⟶ 643:
{{out}}
2 3 5 7 11 13 17 19 23 29 31
=={{header|APL}}==
<syntaxhighlight lang="APL">prime ← 2=0+.=⍳|⊣</syntaxhighlight>
{{out}}
<syntaxhighlight lang="APL"> (⊢(/⍨)prime¨)⍳100
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|AppleScript}}==
Line 675 ⟶ 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 795 ⟶ 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 854 ⟶ 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,040 ⟶ 2,240:
void main() {
iota(2, 40).filter!isPrime3.writeln;
}</syntaxhighlight>
=={{header|Dart}}==
<syntaxhighlight lang="dart">import 'dart:math';
bool isPrime(int n) {
if (n <= 1) return false;
if (n == 2) return true;
for (int i = 2; i <= sqrt(n); ++i) if (n % i == 0) return false;
return true;
}
void main() {
for (int i = 1; i <= 99; ++i) if (isPrime(i)) print('$i ');
}</syntaxhighlight>
Line 2,079 ⟶ 2,293:
Result := True;
end;</syntaxhighlight>
=={{header|Draco}}==
<syntaxhighlight lang="draco">proc prime(word n) bool:
word factor;
bool composite;
if n<=4 then
n=2 or n=3
elif n&1 = 0 then
false
else
factor := 3;
composite := false;
while not composite and factor*factor <= n do
composite := n % factor = 0;
factor := factor + 2
od;
not composite
fi
corp
proc main() void:
word i;
for i from 0 upto 100 do
if prime(i) then
writeln(i)
fi
od
corp</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|E}}==
Line 2,101 ⟶ 2,369:
=={{header|EasyLang}}==
<syntaxhighlight lang="easylang">
func
if
.
if
.
sq = sqrt
while i
if n mod
return 0
.
i += 2
.
.
print isprim 1995937
</syntaxhighlight>
Line 2,767 ⟶ 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) {
val .n = abs(.i)
if .n <= 2: return .n == 2
val .chkdiv =
if .i
return .n ndiv .i and self(.n, .i+2)
}
Line 2,783 ⟶ 3,064:
return .n ndiv 2 and .chkdiv(.n, 3)
}
writeln filter .isPrime, series 100</syntaxhighlight>
Line 2,800 ⟶ 3,069:
{{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|Lingo}}==
Line 2,863 ⟶ 3,131:
=={{header|M2000 Interpreter}}==
<syntaxhighlight lang="m2000 interpreter">
Module Primality_by_trial_division {
Inventory Known1=2@, 3@
IsPrime=lambda Known1 (x as decimal) -> {
=false
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 : =true
Break}
if frac(x/3) else exit
x1=sqrt(x):d = 5@
do
if frac(x/d) else exit
d += 4: if d<= x1 else Append Known1, x : =true: exit
always
}
i=2
While Len(Known1)<20
dummy=Isprime(i)
i++
End While
Print Known1
Print "From
count=0
For i=110 to 130
If isPrime(i) Then Print i, : count++
Next
Print
Print "Found ";count;" primes"
}
Primality_by_trial_division
</syntaxhighlight>
Line 3,045 ⟶ 3,317:
) case
) :prime?</syntaxhighlight>
=={{header|Miranda}}==
<syntaxhighlight lang="miranda">main :: [sys_message]
main = [Stdout (show (filter prime [1..100])),
Stdout "\n"]
prime :: num->bool
prime n = n=2 \/ n=3, if n<=4
= False, if n mod 2=0
= #[d | d<-[3, 5..sqrt n]; n mod d=0]=0, otherwise</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|МК-61/52}}==
Line 3,051 ⟶ 3,335:
3 П4 ИП0 ИП4 / {x} x#0 34 КИП4 КИП4
ИП0 КвКор ИП4 - x<0 16 1 С/П 0 С/П</syntaxhighlight>
=={{header|Modula-2}}==
<syntaxhighlight lang="modula2">MODULE TrialDivision;
FROM InOut IMPORT WriteCard, WriteLn;
CONST
Max = 100;
VAR
i: CARDINAL;
PROCEDURE prime(n: CARDINAL): BOOLEAN;
VAR
factor: CARDINAL;
BEGIN
IF n <= 4 THEN
RETURN (n = 2) OR (n = 3)
ELSIF n MOD 2 = 0 THEN
RETURN FALSE
ELSE
factor := 3;
WHILE factor * factor <= n DO
IF n MOD factor = 0 THEN
RETURN FALSE
END;
INC(factor, 2)
END
END;
RETURN TRUE
END prime;
BEGIN
FOR i := 0 TO Max DO
IF prime(i) THEN
WriteCard(i,3);
WriteLn
END
END
END TrialDivision.</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|MUMPS}}==
Line 3,673 ⟶ 4,021:
(T (> D S) T)
(T (=0 (% N D)) NIL) ) ) ) ) )</syntaxhighlight>
=={{header|PL/0}}==
The program waits for a number. Then it displays 1 if the number is prime, 0 otherwise.
<syntaxhighlight lang="pascal">
var p, isprime;
procedure checkprimality;
var i, isichecked;
begin
isprime := 0;
if p = 2 then isprime := 1;
if p >= 3 then
begin
i := 2; isichecked := 0;
while isichecked = 0 do
begin
if (p / i) * i = p then isichecked := 1;
if isichecked <> 1 then
if i * i >= p then
begin
isprime := 1; isichecked := 1
end;
i := i + 1
end
end
end;
begin
? p;
call checkprimality;
! isprime
end.
</syntaxhighlight>
4 runs:
{{in}}
<pre>1</pre>
{{out}}
<pre> 0</pre>
{{in}}
<pre>25</pre>
{{out}}
<pre> 0</pre>
{{in}}
<pre>43</pre>
{{out}}
<pre> 1</pre>
{{in}}
<pre>101</pre>
{{out}}
<pre> 1</pre>
=={{header|PL/I}}==
Line 3,860 ⟶ 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,078 ⟶ 4,476:
next
return 1</syntaxhighlight>
=={{header|RPL}}==
{{trans|Python}}
This version use binary integers
{{works with|Halcyon Calc|4.2.7}}
{| class="wikitable"
! RPL code
! Comment
|-
|
≪ / 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'''
DUP B→R √ R→B → a maxd
≪ 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
if 2 or 3 divides a
return 0
else
store a and root(a)
initialize stack with a i d and set flag 1 to control loop exit
while d <= root(a)
prepare loop exit if d divides a
i = 6 - i which modifies 2 into 4 and viceversa
empty stack and return result
|}
'''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,462 ⟶ 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,733 ⟶ 5,202:
|4 prime?
=false</syntaxhighlight>
=={{header|Verilog}}==
<syntaxhighlight lang="Verilog">module main;
integer i, k;
initial begin
$display("Prime numbers between 0 and 100:");
for(i = 2; i <= 99; i=i+1) begin
k=i;
if(i[0] != 1'b0) begin
if(k==3 | k==5 | k==7 | k==11 | k==13 | k==17 | k==19) $write(i);
else if(k%3==0 | k%5==0 | k%7==0 | k%11==0 | k%13==0 | k%17==0 | k%19==0) $write("");
else $write(i);
end
if(i==10'b00 | i==10'b010) $write(i);
end
$finish;
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="
var isPrime = Fn.new { |n|
Line 4,752 ⟶ 5,273:
System.print("Are the following prime?")
for (test in tests) {
}</syntaxhighlight>
| |||