Square-free integers: Difference between revisions
Content added Content deleted
Thundergnat (talk | contribs) m (→{{header|Perl 6}}: Minor tweaks.) |
m (→{{header|FreeBASIC}}: changed indents) |
||
Line 240: | Line 240: | ||
For i = 4 To max Step 2 ' prime sieve remove even numbers except 2 |
For i = 4 To max Step 2 ' prime sieve remove even numbers except 2 |
||
sieve(i) = 1 |
|||
Next |
Next |
||
For i = 3 To stop_ Step 2 ' proces odd numbers |
For i = 3 To stop_ Step 2 ' proces odd numbers |
||
If sieve(i) = 0 Then |
|||
For a = i * i To max Step i * 2 |
|||
sieve(a) = 1 |
|||
Next |
|||
End If |
|||
Next |
Next |
||
For i = 2 To max ' move primes to a list |
For i = 2 To max ' move primes to a list |
||
If sieve(i) = 0 Then |
|||
c += 1 |
|||
prime(c) = i |
|||
End If |
|||
Next |
Next |
||
Line 260: | Line 260: | ||
For i = 1 To c ' find all square free integers between 1 and 1000000 |
For i = 1 To c ' find all square free integers between 1 and 1000000 |
||
a = prime(i) * prime(i) |
|||
If a > 1000000 Then Exit For |
|||
For k = a To 1000000 Step a |
|||
list(k) = 1 |
|||
Next |
|||
Next |
Next |
||
k = 0 |
k = 0 |
||
For i = 1 To 145 ' show all between 1 and 145 |
For i = 1 To 145 ' show all between 1 and 145 |
||
If list(i) = 0 Then |
|||
Print Using"####"; i; |
|||
k +=1 |
|||
If k Mod 20 = 0 Then Print |
|||
End If |
|||
Next |
Next |
||
Print : Print |
Print : Print |
||
Line 279: | Line 279: | ||
sieve(0) = 1 ' = trillion |
sieve(0) = 1 ' = trillion |
||
For i = 1 To 5 ' process primes 2, 3, 5, 7, 11 |
For i = 1 To 5 ' process primes 2, 3, 5, 7, 11 |
||
a = prime(i) * prime(i) |
|||
b = a - trillion Mod a |
|||
For k = b To 145 Step a |
|||
sieve(k) = 1 |
|||
Next |
|||
Next |
Next |
||
For i = 6 To c ' process the rest of the primes |
For i = 6 To c ' process the rest of the primes |
||
a = prime(i) * prime(i) |
|||
k = a - trillion Mod a |
|||
If k <= 145 Then sieve(k) = 1 |
|||
Next |
Next |
||
k = 0 |
k = 0 |
||
For i = 0 To 145 |
For i = 0 To 145 |
||
If sieve(i) = 0 Then |
|||
Print Using "################"; (trillion + i); |
|||
k += 1 |
|||
If k Mod 5 = 0 Then print |
|||
End If |
|||
Next |
Next |
||
Print : Print |
Print : Print |
||
Line 304: | Line 304: | ||
a = 1 : b = 100 : k = 0 |
a = 1 : b = 100 : k = 0 |
||
Do Until b > 1000000 ' count them |
Do Until b > 1000000 ' count them |
||
For i = a To b |
|||
If list(i) = 0 Then k += 1 |
|||
Next |
|||
Print "There are "; k; " square free integers between 1 and "; b |
|||
a = b : b *= 10 |
|||
Loop |
Loop |
||