Strong and weak primes: Difference between revisions
Content added Content deleted
Thundergnat (talk | contribs) m (→{{header|Perl 6}}: Style tweaks, DRY) |
(Added Algol 68) |
||
Line 34: | Line 34: | ||
::* The OEIS article: [http://oeis.org/A051635 weak primes]. |
::* The OEIS article: [http://oeis.org/A051635 weak primes]. |
||
<br><br> |
<br><br> |
||
=={{header|ALGOL 68}}== |
|||
{{works with|ALGOL 68G|Any - tested with release 2.8.3.win32}} |
|||
<lang algol68># find and count strong and weak primes # |
|||
PR heap=128M PR # set heap memory size for Algol 68G # |
|||
# returns a string representation of n with commas # |
|||
PROC commatise = ( INT n )STRING: |
|||
BEGIN |
|||
STRING result := ""; |
|||
STRING unformatted = whole( n, 0 ); |
|||
INT ch count := 0; |
|||
FOR c FROM UPB unformatted BY -1 TO LWB unformatted DO |
|||
IF ch count <= 2 THEN ch count +:= 1 |
|||
ELSE ch count := 1; "," +=: result |
|||
FI; |
|||
unformatted[ c ] +=: result |
|||
OD; |
|||
result |
|||
END # commatise # ; |
|||
# sieve values # |
|||
CHAR prime = "P"; # unclassified/average prime # |
|||
CHAR strong = "S"; # strong prime # |
|||
CHAR weak = "W"; # weak prime # |
|||
CHAR composite = "C"; # non-prime # |
|||
# sieve of Eratosthenes: sets s[i] to prime if i is a prime, # |
|||
# composite otherwise # |
|||
PROC sieve = ( REF[]CHAR s )VOID: |
|||
BEGIN |
|||
# start with everything flagged as prime # |
|||
FOR i TO UPB s DO s[ i ] := prime OD; |
|||
# sieve out the non-primes # |
|||
s[ 1 ] := composite; |
|||
FOR i FROM 2 TO ENTIER sqrt( UPB s ) DO |
|||
IF s[ i ] = prime THEN FOR p FROM i * i BY i TO UPB s DO s[ p ] := composite OD FI |
|||
OD |
|||
END # sieve # ; |
|||
INT max number = 10 000 000; |
|||
# construct a sieve of primes up to slightly more than the maximum number # |
|||
# required for the task, as we need an extra prime for the classification # |
|||
[ 1 : max number + 1 000 ]CHAR primes; |
|||
sieve( primes ); |
|||
# classify the primes # |
|||
# find the first three primes # |
|||
INT prev prime := 0; |
|||
INT curr prime := 0; |
|||
INT next prime := 0; |
|||
FOR p FROM 2 WHILE prev prime = 0 DO |
|||
IF primes[ p ] = prime THEN |
|||
prev prime := curr prime; |
|||
curr prime := next prime; |
|||
next prime := p |
|||
FI |
|||
OD; |
|||
# 2 is the only even prime so the first three primes are the only case where # |
|||
# the average of prev prime and next prime is not an integer # |
|||
IF REAL avg = ( prev prime + next prime ) / 2; |
|||
curr prime > avg THEN primes[ curr prime ] := strong |
|||
ELIF curr prime < avg THEN primes[ curr prime ] := weak |
|||
FI; |
|||
# classify the rest of the primes # |
|||
FOR p FROM next prime + 1 WHILE curr prime <= max number DO |
|||
IF primes[ p ] = prime THEN |
|||
prev prime := curr prime; |
|||
curr prime := next prime; |
|||
next prime := p; |
|||
IF INT avg = ( prev prime + next prime ) OVER 2; |
|||
curr prime > avg THEN primes[ curr prime ] := strong |
|||
ELIF curr prime < avg THEN primes[ curr prime ] := weak |
|||
FI |
|||
FI |
|||
OD; |
|||
INT strong1 := 0, strong10 := 0; |
|||
INT weak1 := 0, weak10 := 0; |
|||
FOR p WHILE p < 10 000 000 DO |
|||
IF primes[ p ] = strong THEN |
|||
strong10 +:= 1; |
|||
IF p < 1 000 000 THEN strong1 +:= 1 FI |
|||
ELIF primes[ p ] = weak THEN |
|||
weak10 +:= 1; |
|||
IF p < 1 000 000 THEN weak1 +:= 1 FI |
|||
FI |
|||
OD; |
|||
INT strong count := 0; |
|||
print( ( "first 36 strong primes:", newline ) ); |
|||
FOR p WHILE strong count < 36 DO IF primes[ p ] = strong THEN print( ( " ", whole( p, 0 ) ) ); strong count +:= 1 FI OD; |
|||
print( ( newline ) ); |
|||
print( ( "strong primes below 1,000,000: ", commatise( strong1 ), newline ) ); |
|||
print( ( "strong primes below 10,000,000: ", commatise( strong10 ), newline ) ); |
|||
print( ( "first 37 weak primes:", newline ) ); |
|||
INT weak count := 0; |
|||
FOR p WHILE weak count < 37 DO IF primes[ p ] = weak THEN print( ( " ", whole( p, 0 ) ) ); weak count +:= 1 FI OD; |
|||
print( ( newline ) ); |
|||
print( ( " weak primes below 1,000,000: ", commatise( weak1 ), newline ) ); |
|||
print( ( " weak primes below 10,000,000: ", commatise( weak10 ), newline ) )</lang> |
|||
{{out}} |
|||
<pre> |
|||
first 36 strong primes: |
|||
11 17 29 37 41 59 67 71 79 97 101 107 127 137 149 163 179 191 197 223 227 239 251 269 277 281 307 311 331 347 367 379 397 419 431 439 |
|||
strong primes below 1,000,000: 37,723 |
|||
strong primes below 10,000,000: 320,991 |
|||
first 37 weak primes: |
|||
3 7 13 19 23 31 43 47 61 73 83 89 103 109 113 131 139 151 167 181 193 199 229 233 241 271 283 293 313 317 337 349 353 359 383 389 401 |
|||
weak primes below 1,000,000: 37,780 |
|||
weak primes below 10,000,000: 321,750 |
|||
</pre> |
|||
=={{header|Go}}== |
=={{header|Go}}== |