Sequence of primes by trial division: Difference between revisions
Sequence of primes by trial division (view source)
Revision as of 11:28, 4 February 2024
, 3 months ago→{{header|Wren}}: Minor tidy
(LFE version) |
m (→{{header|Wren}}: Minor tidy) |
||
| (13 intermediate revisions by 10 users not shown) | |||
Line 275:
10: 29
</pre>
=={{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 trialprime.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
ldr r4,iStart @ start number
ldr r5,iLimit @ end number
tst r4,#1
addeq r4,#1
1:
mov r0,r4
ldr r1,iAdrsZoneConv
bl conversion10 @ decimal conversion
ldr r0,iAdrsZoneConv
bl affichageMess
mov r0,r4
bl isPrime
cmp r0,#0
beq 2f
ldr r0,iAdrszMessPrime
bl affichageMess
b 3f
2:
ldr r0,iAdrszMessNotPrime
bl affichageMess
3:
add r4,r4,#2
cmp r4,r5
blt 1b
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 4000000000
iLimit: .int 4000000020
/******************************************************************/
/* 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.
4000000001 is not prime.
4000000003 is not prime.
4000000005 is not prime.
4000000007 is prime.
4000000009 is prime.
4000000011 is not prime.
4000000013 is not prime.
4000000015 is not prime.
4000000017 is not prime.
4000000019 is prime.
</pre>
=={{header|Arturo}}==
Line 547 ⟶ 667:
280: 1823 1831 1847 1861 1867 1871 1873 1877 1879 1889
</pre>
=={{header|bc}}==
<syntaxhighlight lang="bc">l = 100
a[0] = 2
a[o = 1] = 3
for (n = 5; n < l; n += 2) {
for (i = 1; n % (p = a[i]) != 0; ++i) {
if (p * p > n) {
a[++o] = n
break
}
}
}
for (i = 0; i <= o; ++i) a[i]</syntaxhighlight>
=={{header|Befunge}}==
Line 811 ⟶ 947:
=={{header|EasyLang}}==
<syntaxhighlight lang="easylang">
func
if
.
i = 3
while i <=
return 0
.
i += 2
.
.
for i = first to last
.
.
.
primeSequ 2 100 seq[]
print seq[]
</syntaxhighlight>
Line 1,186 ⟶ 1,319:
=={{header|Elena}}==
ELENA
<syntaxhighlight lang="elena">import extensions;
import system'routines;
Line 1,192 ⟶ 1,325:
isPrime =
(n => new Range(2,(n.sqrt() - 1).RoundedInt).allMatchedBy::(i => n.mod
Primes =
(n => new Range(2, n - 2).filterBy
public program()
Line 2,174 ⟶ 2,307:
<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
53 59 61 67 71 73 79 83 89 97 101 103 107 109 113 127 131 137 139 149</pre>
=={{header|M2000 Interpreter}}==
<syntaxhighlight lang="m2000 interpreter">
Module primes_by_trial_division{
inventory Known1=2@, 3@
Global 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/2) else exit
if frac(x/3) else exit
x1=sqrt(x):d = 5@
do
if frac(x/d) else exit
d += 2: if d>x1 then Append Known1, x : =true : exit
if frac(x/d) else exit
d += 4: if d<= x1 else Append Known1, x : =true: exit
always
}
takePrimes=lambda IsPrime, i=2 (n)-> {
flush
while n>0: if isPrime(i) then data i: n--
i++:end while
=array([])
}
report "["+takePrimes(10)#str$(", ")+"]"
m=takePrimes(90) // skip 90 primes
report "["+takePrimes(100)#str$(", ")+"]"
}
primes_by_trial_division
</syntaxhighlight>
{{out}}
<pre>
[2, 3, 5, 7, 11, 13, 17, 19, 23, 29]
[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, 1009, 1013, 1019, 1021, 1031, 1033, 1039, 1049, 1051, 1061, 1063, 1069, 1087, 1091, 1093, 1097, 1103, 1109, 1117, 1123, 1129, 1151, 1153, 1163, 1171, 1181, 1187, 1193, 1201, 1213, 1217, 1223]
</pre>
=={{header|Mathematica}} / {{header|Wolfram Language}}==
Line 2,421 ⟶ 2,592:
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
The 10,001st prime is 104,743
</pre>
=={{header|PL/I-80}}==
<syntaxhighlight lang="PL/I">
/* Prime Number Generator in PLI-80
*
* The logic closely follows an example program by Edsger
* W. Dijkstra in his classic 1969 paper, "Notes on Structured
* Programming." Only odd numbers are checked for primality,
* and only the prime numbers previously found (up to the
* square root of the number under examination) are tested
* as divisors.
*/
primes:
proc options (main);
%replace
maxprimes by 3500, /* practical limit before overflow */
false by '0'b,
true by '1'b;
dcl
p(1:maxprimes) fixed binary(15),
divisible bit(1),
dummy char(1),
(i, k, m, n, s, nprimes, divisor) fixed binary(15);
put skip list ('How many primes do you want? ');
get list (nprimes);
if nprimes > maxprimes then
do;
nprimes = maxprimes;
put skip list ('Only generating',maxprimes,' primes.');
put skip list ('Press CR to continue.');
get edit (dummy) (a);
end;
/* initialize p with first prime number and display it */
p(1) = 2;
put skip list (p(1));
i = 1; /* count of prime numbers found so far */
k = 1; /* index of largest prime <= sqrt of n */
n = 3; /* current number being checked */
do while (i < nprimes);
s = p(k) * p(k);
if s <= n then k = k + 1;
divisible = false;
m = 1; /* index into primes already found */
do while ((m <= k) & (divisible = false));
divisor = p(m); /* can't put p(m) directly into mod()! */
if mod(n, divisor) = 0 then divisible = true;
m = m + 1;
end;
if divisible = false then /* found a prime */
do;
i = i + 1;
p(i) = n;
put list (n);
end;
n = n + 2; /* advance to next odd number */
end;
put skip list ('All done. Goodbye.');
end;
</syntaxhighlight>
{{out}}
<pre>
How many primes do you want? 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
* * *
419 421 431 433 439 443 449 457
461 463 467 479 487 491 499 503
509 521 523 541
All done. Goodbye.
</pre>
Line 2,576 ⟶ 2,824:
primelist = []
def primer(n):
for d in primelist:
break
if n % d == 0:
return
primelist.append(n)
for vv in range(
primer(vv)
print(len(primelist))
print(*primelist)</syntaxhighlight>
{{out}}
<pre>
=={{header|Quackery}}==
Line 2,791 ⟶ 3,037:
return true
</syntaxhighlight>
=={{header|RPL}}==
<code>PRIM?</code> is defined at [[Primality by trial division#RPL|Primality by trial division]]
≪ { } 2 ROT '''FOR''' n
'''IF''' n <span style="color:blue">PRIM?</span> THEN n + '''END'''
'''NEXT'''
≫ '<span style="color:blue">PRIMES</span>' STO
50 <span style="color:blue">PRIMES</span>
{{out}}
<pre>
1: { 2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 }
</pre>
=={{header|Ruby}}==
Line 3,042 ⟶ 3,301:
templates ifPrime
def n: $;
[2..~$n -> $n
end ifPrime
Line 3,079 ⟶ 3,338:
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|uBasic/4tH}}==
{{trans|FreeBASIC}}
<syntaxhighlight lang="uBasic/4tH">' Print all primes from 101 to 999
For i = 101 To 999
If FUNC(_isPrime(i)) Then
Print Using "__# "; i;
EndIf
Next
Print : End
_isPrime
Param (1)
Local (2)
If a@ < 2 Then Return (0)
If a@ = 2 Then Return (1)
If (a@ % 2) = 0 Then Return (0)
b@ = FUNC(_Sqrt(a@, 0))
For c@ = 3 To b@ Step 2
If (a@ % c@) = 0 Then Unloop : Return (0)
Next
Return (1)
_Sqrt
Param (2)
Local (2)
If a@ = 0 Return (0)
c@ = Max(Shl(Set(a@, a@*(10^(b@*2))), -10), 1024)
Do
d@ = (c@+a@/c@)/2
While c@ > d@
c@ = d@
Loop
Return (c@)</syntaxhighlight>
{{Out}}
<pre>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
0 OK, 0:136</pre>
=={{header|V (Vlang)}}==
<syntaxhighlight lang="Vlang">
import math
fn main() {
for idx in 1..101 {if is_prime(idx) {println("${idx}")}}
}
fn is_prime(num int) bool {
if num < 2 {return false}
if num < 4 {return true}
if num % 2 == 0 {return false}
for idx := 3; idx <= math.sqrt(num); idx += 2 {
if num % idx == 0 {return false}
}
return true
}
</syntaxhighlight>
=={{header|Wren}}==
{{libheader|Wren-fmt}}
Using a simple generator.
<syntaxhighlight lang="
var primeSeq = Fiber.new {
| |||