Rosetta Code

Primality by trial division: Difference between revisions

Page Discussion

Primality by trial division (view source)

Revision as of 19:56, 17 June 2024

9,840 bytes added ,  9 days ago
PascalABC.NET
(PascalABC.NET)
(31 intermediate revisions by 12 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 1,028 ⟶ 1,222:
89 is prime
97 is prime</pre>
 
==={{header|GW-BASIC}}===
{{trans|Craft Basic}}
{{works with|PC-BASIC|any}}
{{works with|BASICA}}
{{works with|QBasic}}
{{works with|QB64}}
<syntaxhighlight lang="qbasic">100 FOR I = 1 TO 99
110 IF I < 2 THEN P = 0 : GOTO 180
120 IF I = 2 THEN P = 1 : GOTO 180
130 IF I MOD 2 = 0 THEN P = 0 : GOTO 180
140 P = 1
150 FOR J = 3 TO SQR(I) STEP 2
160 IF I MOD J = 0 THEN P = 0 : GOTO 180
170 NEXT J
180 IF P <> 0 THEN PRINT I;
190 NEXT I
200 END</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|IS-BASIC}}===
Line 1,100 ⟶ 1,314:
{{works with|QBasic|1.1}}
{{works with|QuickBasic|4.5}}
{{works with|QB64}}
Returns 1 for prime, 0 for non-prime
<syntaxhighlight lang="qbasic">' Primality by trial division
Line 2,046 ⟶ 2,261:
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,161 ⟶ 2,390:
=={{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,827 ⟶ 3,057:
 
=={{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)
 
<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">
{{works with|langur|0.11}}
<syntaxhighlight lang="langur">val .isPrime = ffn(.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)
}
return true
}
 
return .n ndiv 2 and .chkdiv(.n, 3)
}
 
writeln filter .(isPrime, series (100</syntaxhighlight>))
</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>
 
{{out}}
Line 2,922 ⟶ 3,154:
=={{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 3,104 ⟶ 3,340:
) 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,627 ⟶ 3,875:
;Output:
2 3 5 7 11 13 17 19 23 29 31 37 41 43 47
 
=={{header|PascalABC.NET}}==
<syntaxhighlight lang="delphi">
function IsPrime(N: integer): boolean;
begin
if N = 1 then
Result := False
else Result := True;
for var i:=2 to N.Sqrt.Round do
if N.Divs(i) then
begin
Result := False;
exit
end;
end;
 
begin
for var i:=1 to 1000 do
if IsPrime(i) then
Print(i)
end.
</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 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|Perl}}==
Line 4,033 ⟶ 4,308:
=={{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,254 ⟶ 4,529:
=={{header|RPL}}==
{{trans|Python}}
This version handlesuse binary integers
{{works with|Halcyon Calc|4.2.7}}
{| class="wikitable"
Line 4,261 ⟶ 4,536:
|-
|
≪ / 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 SWAP #5 1 SF
'''WHILE''' DUP21 '''BDIVFS?''' NOT OVER maxd ≤ AND '''REPEAT'''
'''REPEATIF''' 3a PICKOVER +<span #6style="color:blue">BDIV?</span> 4 ROLL'''THEN''' -1 SWAPCF '''END'''
OVER + #6 ROT - SWAP '''END'''
≫
'''SWAP DROP <span style="color:blue">BDIV?'''</span> NOT SWAP DROP
'''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,287 ⟶ 4,563:
return 0
else
store a and root(a)
initialize stack with i a i d and set flag 1 to control loop exit
while d does not divide a and d <= root(a)
prepare loop exit if d divides a
i = 6 - i which modifies 2 into 4 and viceversa
convertempty stack statusand intoreturn result
|}
'''Floating point version'''
{{in}}
 
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,682 ⟶ 4,971:
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,953 ⟶ 5,252:
|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="ecmascriptwren">import "./fmt" for Fmt
 
var isPrime = Fn.new { |n|
Line 4,972 ⟶ 5,323:
System.print("Are the following prime?")
for (test in tests) {
SystemFmt.print("%(Fmt.d(2$2d -> $y", test)), -> %(isPrime.call(test) ? "yes" : "no")")
}</syntaxhighlight>
 
Miks1965
220

edits

Retrieved from "https://rosettacode.org/wiki/Special:MobileDiff/337217...365484"