Rosetta Code

Sieve of Pritchard: Difference between revisions

Page Discussion

Sieve of Pritchard (view source)

Revision as of 22:33, 24 July 2023

5,097 bytes added ,  9 months ago
Added BASIC256, True BASIC and Yabasic. Grouping BASIC dialects
(Added FreeBasic)
(Added BASIC256, True BASIC and Yabasic. Grouping BASIC dialects)
Line 123:
{{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, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149}</syntaxhighlight>
 
=={{header|BASIC}}==
==={{header|BASIC256}}===
<syntaxhighlight lang="vb">arraybase 1
call sieveOfPritchard(150, true)
call sieveOfPritchard(1e6, false)
end
 
function min(a, b)
if a < b then return a else return b
end function
 
subroutine sieveOfPritchard(limit, imprime)
dim members[limit + 1] fill false
members[1] = true
ub = members[?]
stepLength = 1
prime = 2
rtlim = sqr(limit)
nlimit = 2
dim primes[1]
cont = 0
 
while prime <= rtlim
if stepLength < limit then
for w = 1 to ub
if members[w] then
dim n = w + stepLength
while n <= nlimit
members[n] = true
n += stepLength
end while
end if
next
stepLength = nlimit
end if
 
np = 5
dim mcpy[ub]
for i = 1 to ub
mcpy[i] = members[i]
next
 
for i = 1 to ub
if mcpy[i] then
if np = 5 and i > prime then np = i
dim n = prime * i
if n > limit then exit for
members[n] = false
end if
next
 
if np < prime then exit while
cont += 1
redim primes(cont)
primes[cont] = prime
if prime = 2 then prime = 3 else prime = np
nlimit = min(stepLength * prime, limit)
end while
 
dim newPrimes(ub)
for i = 2 to ub
if members[i] then newPrimes[i] = i
next
 
cont = 0
for i = 1 to primes[?]
if imprime then print " "; primes[i];
cont += 1
next
for i = 1 to ub
if newPrimes[i] then
cont += 1
if imprime then print " "; i;
end if
next
if not imprime then print : print "Number of primes up to "; limit; ": "; cont
end subroutine</syntaxhighlight>
{{out}}
<pre>Similar to FreeBASIC entry.</pre>
 
==={{header|FreeBASIC}}===
{{trans|Wren}}
<syntaxhighlight lang="vb">#define min(a, b) iif((a) < (b), (a), (b))
 
Sub sieveOfPritchard(limit As Uinteger, imprime As Boolean)
Dim As Boolean members(1 To limit + 1)
members(1) = True
Dim As Uinteger ub = Ubound(members)
Dim As Uinteger stepLength = 1
Dim As Uinteger prime = 2
Dim As Uinteger rtlim = Sqr(limit)
Dim As Uinteger nlimit = 2
Dim As Integer primes()
Dim As Integer i, cont = 0
While prime <= rtlim
If stepLength < limit Then
For w As Integer = 1 To ub
If members(w) Then
Dim As Integer n = w + stepLength
While n <= nlimit
members(n) = True
n += stepLength
Wend
End If
Next
stepLength = nlimit
End If
Dim As Uinteger np = 5
Dim As Boolean mcpy(ub)
For i = 1 To ub
mcpy(i) = members(i)
Next
For i = 1 To ub
If mcpy(i) Then
If np = 5 And i > prime Then np = i
Dim As Uinteger n = prime * i
If n > limit Then Exit For there.
members(n) = False
End If
Next
If np < prime Then Exit While
cont += 1
Redim Preserve primes(cont)
primes(cont) = prime
prime = Iif(prime = 2, 3, np)
nlimit = min(stepLength * prime, limit)
Wend
Dim As Integer newPrimes(ub)
For i = 2 To ub
If members(i) Then newPrimes(i) = i
Next
cont = 0
For i = 1 To Ubound(primes)
If imprime Then Print primes(i);
cont += 1
Next
For i = 1 To ub
If newPrimes(i) Then
cont += 1
If imprime Then Print i;
End If
Next
If Not imprime Then Print !"\nNumber of primes up to "; limit; ":"; cont
End Sub
 
sieveOfPritchard(150, True)
sieveOfPritchard(1e6, False)
 
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 101 103 107 109 113 127 131 137 139 149
Number of primes up to 1000000: 78498</pre>
 
==={{header|True BASIC}}===
<syntaxhighlight lang="qbasic">FUNCTION min(a, b)
IF a < b THEN LET min = a ELSE LET min = b
END FUNCTION
 
SUB sieveofpritchard (limit)
DIM members(0)
MAT REDIM members(limit+1)
LET members(1) = 1
LET ub = UBOUND(members)
LET steplength = 1
LET prime = 2
LET rtlim = SQR(limit)
LET nlimit = 2
DIM primes(10)
LET cnt = 0
DIM mcpy(0)
MAT REDIM mcpy(ub)
 
DO WHILE prime <= rtlim
IF steplength < limit THEN
FOR w = 1 TO ub
IF members(w)<>0 THEN
LET n = w+steplength
DO WHILE n <= nlimit
LET members(n) = 1
LET n = n+steplength
LOOP
END IF
NEXT w
LET steplength = nlimit
END IF
 
LET np = 5
FOR i = 1 TO ub
LET mcpy(i) = members(i)
NEXT i
 
FOR i = 1 TO ub
IF mcpy(i)<>0 THEN
IF np = 5 AND i > prime THEN LET np = i
LET n = prime*i
IF n > limit THEN EXIT FOR
LET members(n) = 0
END IF
NEXT i
 
IF np < prime THEN EXIT DO
LET cnt = cnt+1
MAT REDIM primes(cnt)
LET primes(cnt) = prime
IF prime = 2 THEN LET prime = 3 ELSE LET prime = np
LET nlimit = min(steplength*prime, limit)
LOOP
 
DIM newprimes(0)
MAT REDIM newprimes(ub)
FOR i = 2 TO ub
IF members(i)<>0 THEN LET newprimes(i) = i
NEXT i
 
LET cnt = 0
FOR i = 1 TO UBOUND(primes)
PRINT primes(i);
LET cnt = cnt+1
NEXT i
FOR i = 1 TO ub
IF newprimes(i)<>0 THEN
PRINT i;
LET cnt = cnt+1
END IF
NEXT i
END SUB
 
CLEAR
CALL sieveofpritchard (150)
END</syntaxhighlight>
{{out}}
<pre>Similar to FreeBASIC entry.</pre>
 
==={{header|Yabasic}}===
<syntaxhighlight lang="vb">sieveOfPritchard(150, true)
sieveOfPritchard(1e6, false)
end
 
sub sieveOfPritchard(limit, imprime)
dim members(limit + 1)
members(1) = true
ub = arraysize(members(),1)
stepLength = 1
prime = 2
rtlim = sqrt(limit)
nlimit = 2
dim primes(1)
cont = 0
 
while prime <= rtlim
if stepLength < limit then
for w = 1 to ub
if members(w) then
n = w + stepLength
while n <= nlimit
members(n) = true
n = n + stepLength
wend
fi
next
stepLength = nlimit
fi
 
np = 5
dim mcpy(ub)
for i = 1 to ub
mcpy(i) = members(i)
next
 
for i = 1 to ub
if mcpy(i) then
if np = 5 and i > prime np = i
n = prime * i
if n > limit break
members(n) = false
fi
next
 
if np < prime break
cont = cont + 1
redim primes(cont)
primes(cont) = prime
if prime = 2 then prime = 3 else prime = np : fi
nlimit = min(stepLength * prime, limit)
wend
 
dim newPrimes(ub)
for i = 2 to ub
if members(i) newPrimes(i) = i
next
 
cont = 0
for i = 1 to arraysize(primes(),1)
if imprime print " ", primes(i);
cont = cont + 1
next
for i = 1 to ub
if newPrimes(i) then
cont = cont + 1
if imprime print " ", i;
fi
next
if not imprime then print : print "Number of primes up to ", limit, ": ", cont : fi
end sub</syntaxhighlight>
{{out}}
<pre>Similar to FreeBASIC entry.</pre>
 
 
=={{header|C#|CSharp}}==
Line 332 ⟶ 646:
35 primes up to 150 found in 0.038 ms using array w[40]
 
50847534 primes up to 1000000000 found in 2339.566 ms using array w[163588196]</pre>
</pre>
 
=={{header|FreeBASIC}}==
{{trans|Wren}}
<syntaxhighlight lang="vb">#define min(a, b) iif((a) < (b), (a), (b))
 
Sub sieveOfPritchard(limit As Uinteger, imprime As Boolean)
Dim As Boolean members(1 To limit + 1)
members(1) = True
Dim As Uinteger ub = Ubound(members)
Dim As Uinteger stepLength = 1
Dim As Uinteger prime = 2
Dim As Uinteger rtlim = Sqr(limit)
Dim As Uinteger nlimit = 2
Dim As Integer primes()
Dim As Integer i, cont = 0
While prime <= rtlim
If stepLength < limit Then
For w As Integer = 1 To ub
If members(w) Then
Dim As Integer n = w + stepLength
While n <= nlimit
members(n) = True
n += stepLength
Wend
End If
Next
stepLength = nlimit
End If
Dim As Uinteger np = 5
Dim As Boolean mcpy(ub)
For i = 1 To ub
mcpy(i) = members(i)
Next
For i = 1 To ub
If mcpy(i) Then
If np = 5 And i > prime Then np = i
Dim As Uinteger n = prime * i
If n > limit Then Exit For there.
members(n) = False
End If
Next
If np < prime Then Exit While
cont += 1
Redim Preserve primes(cont)
primes(cont) = prime
prime = Iif(prime = 2, 3, np)
nlimit = min(stepLength * prime, limit)
Wend
Dim As Integer newPrimes(ub)
For i = 2 To ub
If members(i) Then newPrimes(i) = i
Next
cont = 0
For i = 1 To Ubound(primes)
If imprime Then Print primes(i);
cont += 1
Next
For i = 1 To ub
If newPrimes(i) Then
cont += 1
If imprime Then Print i;
End If
Next
If Not imprime Then Print !"\nNumber of primes up to "; limit; ":"; cont
End Sub
 
sieveOfPritchard(150, True)
sieveOfPritchard(1e6, False)
 
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 101 103 107 109 113 127 131 137 139 149
Number of primes up to 1000000: 78498</pre>
 
=={{header|J}}==
Jjuanhdez
2,122

edits

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