Primality by trial division: Difference between revisions
→Functional
Jazzedpineda (talk | contribs) (Add EasyLang) |
Langurmonkey (talk | contribs) |
||
| (45 intermediate revisions by 17 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}}
<syntaxhighlight lang="freebasic">for i = 1 to 99
if isPrime(i) then print string(i); " ";
next i
end
function isPrime(v)
if v < 2 then return False
if v mod 2 = 0 then return v = 2
if v mod 3 = 0 then return v = 3
d = 5
while d * d <= v
if v mod d = 0 then return False else d += 2
end while
return True
end function</syntaxhighlight>
==={{header|BBC BASIC}}===
<syntaxhighlight lang="bbcbasic"> FOR i% = -1 TO 100
IF FNisprime(i%) PRINT ; i% " is prime"
NEXT
END
DEF FNisprime(n%)
IF n% <= 1 THEN = FALSE
IF n% <= 3 THEN = TRUE
IF (n% AND 1) = 0 THEN = FALSE
LOCAL t%
FOR t% = 3 TO SQR(n%) STEP 2
IF n% MOD t% = 0 THEN = FALSE
NEXT
= TRUE</syntaxhighlight>
{{out}}
<pre>2 is prime
3 is prime
5 is prime
7 is prime
11 is prime
13 is prime
17 is prime
19 is prime
23 is prime
29 is prime
31 is prime
37 is prime
41 is prime
43 is prime
47 is prime
53 is prime
59 is prime
61 is prime
67 is prime
71 is prime
73 is prime
79 is prime
83 is prime
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}}===
The second function (included by not used) I would have thought would be faster because it lacks the SQR() function. As it happens, the first is over twice as fast.
<syntaxhighlight lang="qbasic">#APPTYPE CONSOLE
FUNCTION ISPRIME(n AS INTEGER) AS INTEGER
IF n = 2 THEN
RETURN TRUE
ELSEIF n <= 1 ORELSE n MOD 2 = 0 THEN
RETURN FALSE
ELSE
FOR DIM i = 3 TO SQR(n) STEP 2
IF n MOD i = 0 THEN
RETURN FALSE
END IF
NEXT
RETURN TRUE
END IF
END FUNCTION
FUNCTION ISPRIME2(N AS INTEGER) AS INTEGER
IF N <= 1 THEN RETURN FALSE
DIM I AS INTEGER = 2
WHILE I * I <= N
IF N MOD I = 0 THEN
RETURN FALSE
END IF
I = I + 1
WEND
RETURN TRUE
END FUNCTION
' Test and display primes 1 .. 50
DIM n AS INTEGER
FOR n = 1 TO 50
IF
PRINT n, " ";
END IF
NEXT
PAUSE</syntaxhighlight>
{{out}}
<pre>
2 3 5 7 11 13 17 19 23 29 31 37 41 43 47
Press any key to continue...
</pre>
==={{header|FreeBASIC}}===
<syntaxhighlight lang="freebasic">' FB 1.05.0 Win64
Function isPrime(n As Integer) As Boolean
If n < 2 Then Return False
If n = 2 Then Return True
If n Mod 2 = 0 Then Return False
Dim limit As Integer = Sqr(n)
For i As Integer = 3 To limit Step 2
If n Mod i = 0 Then Return False
Next
Return True
End Function
' To test this works, print all primes under 100
For i As Integer = 1 To 99
If isPrime(i) Then
Print Str(i); " ";
End If
Next
Print : Print
Print "Press any key to quit"
Sleep</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|FutureBasic}}===
<syntaxhighlight lang="futurebasic">window 1, @"Primality By Trial Division", (0,0,480,270)
local fn isPrime( n as long ) as Boolean
long i
Boolean result
if n < 2 then result = NO : exit fn
if n = 2 then result = YES : exit fn
if n mod 2 == 0 then result = NO : exit fn
result = YES
for i = 3 to int( n^.5 ) step 2
if n mod i == 0 then result = NO : break
next i
end fn = result
long i, j = 0
print "Prime numbers between 0 and 1000:"
for i = 0 to 1000
if ( fn isPrime(i) != _false )
printf @"%3d\t",i : j++
if j mod 10 == 0 then print
end if
next
HandleEvents</syntaxhighlight>
{{out}}
<pre>
Prime numbers between 0 and 1000:
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 101 103 107 109 113
127 131 137 139 149 151 157 163 167 173
179 181 191 193 197 199 211 223 227 229
233 239 241 251 257 263 269 271 277 281
283 293 307 311 313 317 331 337 347 349
353 359 367 373 379 383 389 397 401 409
419 421 431 433 439 443 449 457 461 463
467 479 487 491 499 503 509 521 523 541
547 557 563 569 571 577 587 593 599 601
607 613 617 619 631 641 643 647 653 659
661 673 677 683 691 701 709 719 727 733
739 743 751 757 761 769 773 787 797 809
811 821 823 827 829 839 853 857 859 863
877 881 883 887 907 911 919 929 937 941
947 953 967 971 977 983 991 997
</pre>
==={{header|Gambas}}===
'''[https://gambas-playground.proko.eu/?gist=85fbc7936b17b3009af282752aa29df7 Click this link to run this code]'''
<syntaxhighlight lang="gambas">'Reworked from the BBC Basic example
Public Sub Main()
Dim iNum As Integer
For iNum = 1 To 100
If FNisprime(iNum) Then Print iNum & " is prime"
Next
End
'___________________________________________________
Public Sub FNisprime(iNum As Integer) As Boolean
Dim iLoop As Integer
Dim bReturn As Boolean = True
If iNum <= 1 Then bReturn = False
If iNum <= 3 Then bReturn = True
If (iNum And 1) = 0 Then bReturn = False
For iLoop = 3 To Sqr(iNum) Step 2
If iNum Mod iLoop = 0 Then bReturn = False
Next
Return bReturn
End</syntaxhighlight>
{{out}}
<pre>1 is prime
3 is prime
5 is prime
7 is prime
11 is prime
......
73 is prime
79 is prime
83 is prime
89 is prime
97 is prime</pre>
==={{header|IS-BASIC}}===
Line 840 ⟶ 1,240:
240 END IF
250 END DEF</syntaxhighlight>
==={{header|Liberty BASIC}}===
{{works with|Just BASIC}}
<syntaxhighlight lang="lb">print "Rosetta Code - Primality by trial division"
print
[start]
input "Enter an integer: "; x
if x=0 then print "Program complete.": end
if isPrime(x) then print x; " is prime" else print x; " is not prime"
goto [start]
function isPrime(p)
p=int(abs(p))
if p=2 then isPrime=1: exit function 'prime
if p=0 or p=1 or (p mod 2)=0 then exit function 'not prime
for i=3 to sqr(p) step 2
if (p mod i)=0 then exit function 'not prime
next i
isPrime=1
end function</syntaxhighlight>
{{out}}
<pre>Rosetta Code - Primality by trial division
Enter an integer: 1
1 is not prime
Enter an integer: 2
2 is prime
Enter an integer:
Program complete.</pre>
==={{header|PureBasic}}===
<syntaxhighlight lang="purebasic">Procedure.i IsPrime(n)
Protected k
If n = 2
ProcedureReturn #True
EndIf
If n <= 1 Or n % 2 = 0
ProcedureReturn #False
EndIf
For k = 3 To Int(Sqr(n)) Step 2
If n % k = 0
ProcedureReturn #False
EndIf
Next
ProcedureReturn #True
EndProcedure</syntaxhighlight>
==={{header|QuickBASIC}}===
{{works with|QBasic|1.1}}
{{works with|QuickBasic|4.5}}
Returns 1 for prime, 0 for non-prime
<syntaxhighlight lang="qbasic">' Primality by trial division
' Test and display primes 1 .. 50
DECLARE FUNCTION prime% (n!)
FOR n = 1 TO 50
IF prime(n) = 1 THEN PRINT n;
NEXT n
FUNCTION prime% (n!)
STATIC i AS INTEGER
IF n = 2 THEN
prime = 1
ELSEIF n <= 1 OR n MOD 2 = 0 THEN
prime = 0
ELSE
prime = 1
FOR i = 3 TO INT(SQR(n)) STEP 2
IF n MOD i = 0 THEN
prime = 0
EXIT FUNCTION
END IF
NEXT i
END IF
END FUNCTION</syntaxhighlight>
{{out}}
<pre>
2 3 5 7 11 13 17 19 23 29 31 37 41 43 47
</pre>
==={{header|Run BASIC}}===
{{works with|Just BASIC}}
<syntaxhighlight lang="runbasic">' Test and display primes 1 .. 50
for i = 1 TO 50
if prime(i) <> 0 then print i;" ";
next i
FUNCTION prime(n)
if n < 2 then prime = 0 : goto [exit]
if n = 2 then prime = 1 : goto [exit]
if n mod 2 = 0 then prime = 0 : goto [exit]
prime = 1
for i = 3 to int(n^.5) step 2
if n mod i = 0 then prime = 0 : goto [exit]
next i
[exit]
END FUNCTION</syntaxhighlight>
{{out}}
<pre>
2 3 5 7 11 13 17 19 23 25 29 31 37 41 43 47
</pre>
==={{header|S-BASIC}}===
<syntaxhighlight lang="s-basic">
$lines
$constant FALSE = 0
$constant TRUE = 0FFFFH
rem - return p mod q
function mod(p, q = integer) = integer
end = p - q * (p / q)
rem - return true (-1) if n is prime, otherwise false (0)
function isprime(n = integer) = integer
var i, limit, result = integer
if n = 2 then
result = TRUE
else if (n < 2) or (mod(n,2) = 0) then
result = FALSE
else
begin
limit = int(sqr(n))
i = 3
while (i <= limit) and (mod(n, i) <> 0) do
i = i + 2
result = not (i <= limit)
end
end = result
rem - test by looking for primes in range 1 to 50
var i = integer
for i = 1 to 50
if isprime(i) then print using "#####";i;
next i
end
</syntaxhighlight>
{{out}}
<pre>
2 3 5 7 11 13 17 19 23 29 31 37 41 43 47
</pre>
==={{header|TI-83 BASIC}}===
Prompt A
If A=2:Then
Disp "PRIME"
Stop
End
If (fPart(A/2)=0 and A>0) or A<2:Then
Disp "NOT PRIME"
Stop
End
1→P
For(B,3,int(√(A)))
If FPart(A/B)=0:Then
0→P
√(A)→B
End
B+1→B
End
If P=1:Then
Disp "PRIME"
Else
Disp "NOT PRIME"
End
==={{header|Tiny BASIC}}===
{{works with|TinyBasic}}
<syntaxhighlight lang="basic">10 REM Primality by trial division
20 PRINT "Enter a number "
30 INPUT P
40 GOSUB 1000
50 IF Z = 1 THEN PRINT "It is prime."
60 IF Z = 0 THEN PRINT "It is not prime."
70 END
990 REM Primality of the number P by trial division
1000 IF P < 2 THEN RETURN
1010 LET Z = 1
1020 IF P < 4 THEN RETURN
1030 LET I = 2
1040 IF (P / I) * I = P THEN LET Z = 0
1050 IF Z = 0 THEN RETURN
1060 LET I = I + 1
1070 IF I * I <= P THEN GOTO 1040
1080 RETURN</syntaxhighlight>
==={{header|True BASIC}}===
{{trans|
<syntaxhighlight lang="qbasic">FUNCTION isPrime (n)
IF n = 2 THEN
Line 863 ⟶ 1,457:
NEXT n
END</syntaxhighlight>
==={{header|uBasic/4tH}}===
<syntaxhighlight lang="text">10 LET n=0: LET p=0
20 INPUT "Enter number: ";n
30 LET p=0 : IF n>1 THEN GOSUB 1000
40 IF p=0 THEN PRINT n;" is not prime!"
50 IF p#0 THEN PRINT n;" is prime!"
60 GOTO 10
1000 REM ***************
1001 REM * PRIME CHECK *
1002 REM ***************
1010 LET p=0
1020 IF (n%2)=0 THEN RETURN
1030 LET p=1 : PUSH n,0 : GOSUB 9030
1040 FOR i=3 TO POP() STEP 2
1050 IF (n%i)=0 THEN LET p=0: PUSH n,0 : GOSUB 9030 : LET i=POP()
1060 NEXT i
1070 RETURN
9030 Push ((10^(Pop()*2))*Pop()) : @(255)=Tos()
9040 Push (@(255) + (Tos()/@(255)))/2
If Abs(@(255)-Tos())<2 Then @(255)=Pop() : If Pop() Then Push @(255) : Return
@(255) = Pop() : Goto 9040
REM ** This is an integer SQR subroutine. Output is scaled by 10^(TOS()).</syntaxhighlight>
==={{header|VBA}}===
<syntaxhighlight lang="vb">Option Explicit
Sub FirstTwentyPrimes()
Dim count As Integer, i As Long, t(19) As String
Do
i = i + 1
If IsPrime(i) Then
t(count) = i
count = count + 1
End If
Loop While count <= UBound(t)
Debug.Print Join(t, ", ")
End Sub
Function IsPrime(Nb As Long) As Boolean
If Nb = 2 Then
IsPrime = True
ElseIf Nb < 2 Or Nb Mod 2 = 0 Then
Exit Function
Else
Dim i As Long
For i = 3 To Sqr(Nb) Step 2
If Nb Mod i = 0 Then Exit Function
Next
IsPrime = True
End If
End Function</syntaxhighlight>
{{out}}
<pre>
2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71
</pre>
==={{header|VBScript}}===
{{trans|QuickBASIC}}
<syntaxhighlight lang="vb">Function IsPrime(n)
If n = 2 Then
IsPrime = True
ElseIf n <= 1 Or n Mod 2 = 0 Then
IsPrime = False
Else
IsPrime = True
For i = 3 To Int(Sqr(n)) Step 2
If n Mod i = 0 Then
IsPrime = False
Exit For
End If
Next
End If
End Function
For n = 1 To 50
If IsPrime(n) Then
WScript.StdOut.Write n & " "
End If
Next</syntaxhighlight>
{{out}}
<pre>
2 3 5 7 11 13 17 19 23 29 31 37 41 43 47
</pre>
==={{header|Yabasic}}===
{{trans|FreeBASIC}}
<syntaxhighlight lang="yabasic">for i = 1 to 99
if isPrime(i) print str$(i), " ";
next i
print
end
sub isPrime(v)
if v < 2 return False
if mod(v, 2) = 0 return v = 2
if mod(v, 3) = 0 return v = 3
d = 5
while d * d <= v
if mod(v, d) = 0 then return False else d = d + 2 : fi
wend
return True
end sub</syntaxhighlight>
==={{header|ZX Spectrum Basic}}===
Line 888 ⟶ 1,585:
119 is not prime!
137 is prime!</pre>
=={{header|bc}}==
Line 1,314 ⟶ 1,951:
7 is a prime number
8 is not a prime number
=={{header|Cowgol}}==
<syntaxhighlight lang="cowgol">include "cowgol.coh";
sub prime(n: uint32): (isprime: uint8) is
isprime := 1;
if n < 2 then
isprime := 0;
return;
end if;
if n & 1 == 0 then
if n != 2 then
isprime := 0;
end if;
return;
end if;
var factor: uint32 := 3;
while factor * factor <= n loop
if n % factor == 0 then
isprime := 0;
return;
end if;
factor := factor + 2;
end loop;
end sub;
var i: uint32 := 0;
while i <= 100 loop
if prime(i) != 0 then
print_i32(i);
print_nl();
end if;
i := i + 1;
end loop;</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|Crystal}}==
Line 1,474 ⟶ 2,174:
<syntaxhighlight lang="d">import std.stdio, std.algorithm, std.range, std.math;
bool isPrime1(T)(in
return true;
if (n <= 1 || (n & 1) == 0)
return false;
for(
if (n % i == 0)
return false;
return true;
}
void main() {
Line 1,491 ⟶ 2,194:
{{out}}
[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37]
===Version with excluded multiplies of 2 and 3===
Same output.
Line 1,536 ⟶ 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 1,575 ⟶ 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 1,597 ⟶ 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 1,906 ⟶ 2,679:
]?]?%]p:</syntaxhighlight>
=={{header|Forth}}==
<syntaxhighlight lang="forth">: prime? ( n -- f )
dup 2 < if drop false
Line 1,986 ⟶ 2,714:
END IF
END FUNCTION</syntaxhighlight>
=={{header|Frink}}==
Line 2,029 ⟶ 2,729:
return true
}</syntaxhighlight>
=={{header|FunL}}==
Line 2,045 ⟶ 2,744:
10000000033
=={{header|GAP}}==
Line 2,362 ⟶ 2,974:
{{out}}
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
=={{header|Lambdatalk}}==
<syntaxhighlight lang="scheme">
1) the simplest
{def isprime1
{def isprime1.loop
{lambda {:n :m :i}
{if {> :i :m}
then true
else {if {= {% :n :i} 0}
then false
else {isprime1.loop :n :m {+ :i 1}} }
}}}
{lambda {:n}
{isprime1.loop :n {sqrt :n} 2}
}}
-> isprime1
2) slightly improved
{def isprime2
{def isprime2.loop
{lambda {:n :m :i}
{if {> :i :m}
then true
else {if {= {% :n :i} 0}
then false
else {isprime2.loop :n :m {+ :i 2}}
}}}}
{lambda {:n}
{if {or {= :n 2} {= :n 3} {= :n 5} {= :n 7}}
then true
else {if {or {< : n 2} {= {% :n 2} 0}}
then false
else {isprime2.loop :n {sqrt :n} 3}
}}}}
-> isprime2
3) testing
{isprime1 1299709} -> stackoverflow on my iPad Pro
{isprime2 1299709} -> true
{def primesTo
{lambda {:f :n}
{S.replace \s by space in
{S.map {{lambda {:f :i} {if {:f :i} then :i else}} :f}
{S.serie 2 :n}}} }}
-> primesTo
{primesTo isprime1 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 in 25ms
{primesTo isprime2 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 in 20ms
{primesTo isprime1 1000000} in about 30000ms
{primesTo isprime2 1000000} in about 15000ms
</syntaxhighlight>
=={{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,380 ⟶ 3,064:
return .n ndiv 2 and .chkdiv(.n, 3)
}
writeln filter .isPrime, series 100</syntaxhighlight>
Line 2,397 ⟶ 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,487 ⟶ 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 2,538 ⟶ 3,186:
0
1
=={{header|MAD}}==
<syntaxhighlight lang="MAD"> NORMAL MODE IS INTEGER
INTERNAL FUNCTION(N)
ENTRY TO PRIME.
WHENEVER N.L.2, FUNCTION RETURN 0B
WHENEVER N.E.N/2*2, FUNCTION RETURN N.E.2
THROUGH TRIAL, FOR FAC=3, 2, FAC*FAC.G.N
TRIAL WHENEVER N.E.N/FAC*FAC, FUNCTION RETURN 0B
FUNCTION RETURN 1B
END OF FUNCTION
PRINT COMMENT $ PRIMES UNDER 100 $
THROUGH CAND, FOR C=0, 1, C.G.100
CAND WHENEVER PRIME.(C), PRINT FORMAT PR,C
VECTOR VALUES PR = $ I3*$
END OF PROGRAM</syntaxhighlight>
{{out}}
<pre>PRIMES UNDER 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</pre>
=={{header|Maple}}==
Line 2,623 ⟶ 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 2,629 ⟶ 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 2,899 ⟶ 3,669:
=={{header|OCaml}}==
<syntaxhighlight lang="ocaml">let is_prime n =
if n
then n lor 1 = 3
else n land 1
=={{header|Octave}}==
Line 3,034 ⟶ 3,802:
=={{header|Pascal}}==
{{trans|
<syntaxhighlight lang="pascal">program primes;
Line 3,253 ⟶ 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,389 ⟶ 4,207:
?-</pre>
=={{header|Python}}==
Line 3,461 ⟶ 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 3,679 ⟶ 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 3,898 ⟶ 4,756:
primep3?: 0.4 i/s - 1.97x slower
</pre>
=={{header|Rust}}==
Line 3,938 ⟶ 4,778:
<pre>2 3 5 7 11 13 17 19 23 29 </pre>
=={{header|S-lang}}==
Line 4,121 ⟶ 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,178 ⟶ 4,988:
{{out}}
2 3 5 7 11 13 17 19 23 29 31 37 41 43 47
=={{header|SparForte}}==
As a structured script.
<syntaxhighlight lang="ada">#!/usr/local/bin/spar
pragma annotate( summary, "prime" );
pragma annotate( description, "Write a boolean function that tells whether a given" );
pragma annotate( description, "integer is prime. Remember that 1 and all" );
pragma annotate( description, "non-positive numbers are not prime. " );
pragma annotate( see_also, "http://rosettacode.org/wiki/Primality_by_trial_division" );
pragma annotate( author, "Ken O. Burtch" );
pragma license( unrestricted );
pragma restriction( no_external_commands );
procedure prime is
function is_prime(item : positive) return boolean is
result : boolean := true;
test : natural;
begin
if item /= 2 and item mod 2 = 0 then
result := false;
else
test := 3;
while test < natural( numerics.sqrt( item ) ) loop
if natural(item) mod test = 0 then
result := false;
exit;
end if;
test := @ + 2;
end loop;
end if;
return result;
end is_prime;
number : positive;
result : boolean;
begin
number := 6;
result := is_prime( number );
put( number ) @ ( " : " ) @ ( result );
new_line;
number := 7;
result := is_prime( number );
put( number ) @ ( " : " ) @ ( result );
new_line;
number := 8;
result := is_prime( number );
put( number ) @ ( " : " ) @ ( result );
new_line;
end prime;</syntaxhighlight>
=={{header|SQL}}==
Line 4,273 ⟶ 5,137:
return true
}</syntaxhighlight>
=={{header|UNIX Shell}}==
Line 4,408 ⟶ 5,203:
=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 <=
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() {
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,483 ⟶ 5,273:
System.print("Are the following prime?")
for (test in tests) {
}</syntaxhighlight>
Line 4,520 ⟶ 5,310:
0
not prime</pre>
=={{header|zkl}}==
| |||