Strong and weak primes: Difference between revisions
m C++ - use ostream_iterator to print list of primes |
No edit summary |
||
Line 1,436: | Line 1,436: | ||
37,780 weak primes below 1,000,000 |
37,780 weak primes below 1,000,000 |
||
321,750 weak primes below 10,000,000 |
321,750 weak primes below 10,000,000 |
||
</pre> |
|||
=={{header|PureBasic}}== |
|||
<lang PureBasic>#MAX=10000000+20 |
|||
Global Dim P.b(#MAX) : FillMemory(@P(),#MAX,1,#PB_Byte) |
|||
Global NewList Primes.i() |
|||
Global NewList Strong.i() |
|||
Global NewList Weak.i() |
|||
For n=2 To Sqr(#MAX)+1 : If P(n) : m=n*n : While m<=#MAX : P(m)=0 : m+n : Wend : EndIf : Next |
|||
For i=2 To #MAX : If p(i) : AddElement(Primes()) : Primes()=i : EndIf : Next |
|||
If FirstElement(Primes()) |
|||
pp=Primes() |
|||
While NextElement(Primes()) |
|||
ap=Primes() |
|||
If NextElement(Primes()) : np=Primes() : Else : Break : EndIf |
|||
If ap>(pp+np)/2.0 : AddElement(Strong()) : Strong()=ap : If ap<1000000 : c1+1 : EndIf : EndIf |
|||
If ap<(pp+np)/2.0 : AddElement(Weak()) : Weak()=ap : If ap<1000000 : c2+1 : EndIf : EndIf |
|||
PreviousElement(Primes()) : pp=Primes() |
|||
Wend |
|||
EndIf |
|||
OpenConsole() |
|||
If FirstElement(Strong()) |
|||
PrintN("First 36 strong primes:") |
|||
Print(Str(Strong())+" ") |
|||
For i=2 To 36 : If NextElement(Strong()) : Print(Str(Strong())+" ") : Else : Break : EndIf : Next |
|||
PrintN("") |
|||
EndIf |
|||
PrintN("Number of strong primes below 1'000'000 = "+FormatNumber(c1,0,".","'")) |
|||
PrintN("Number of strong primes below 10'000'000 = "+FormatNumber(ListSize(Strong()),0,".","'")) |
|||
If FirstElement(Weak()) |
|||
PrintN("First 37 weak primes:") |
|||
Print(Str(Weak())+" ") |
|||
For i=2 To 37 : If NextElement(Weak()) : Print(Str(Weak())+" ") : Else : Break : EndIf : Next |
|||
PrintN("") |
|||
EndIf |
|||
PrintN("Number of weak primes below 1'000'000 = "+FormatNumber(c2,0,".","'")) |
|||
PrintN("Number of weak primes below 10'000'000 = "+FormatNumber(ListSize(Weak()),0,".","'")) |
|||
Input()</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 |
|||
Number of strong primes below 1'000'000 = 37'723 |
|||
Number of 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 |
|||
Number of weak primes below 1'000'000 = 37'780 |
|||
Number of weak primes below 10'000'000 = 321'750 |
|||
</pre> |
</pre> |
||
Revision as of 22:58, 4 April 2021
![Task](http://static.miraheze.org/rosettacodewiki/thumb/b/ba/Rcode-button-task-crushed.png/64px-Rcode-button-task-crushed.png)
You are encouraged to solve this task according to the task description, using any language you may know.
- Definitions (as per number theory)
-
- The prime(p) is the pth prime.
- prime(1) is 2
- prime(4) is 7
- A strong prime is when prime(p) is > [prime(p-1) + prime(p+1)] ÷ 2
- A weak prime is when prime(p) is < [prime(p-1) + prime(p+1)] ÷ 2
Note that the definition for strong primes is different when used in the context of cryptography.
- Task
-
- Find and display (on one line) the first 36 strong primes.
- Find and display the count of the strong primes below 1,000,000.
- Find and display the count of the strong primes below 10,000,000.
- Find and display (on one line) the first 37 weak primes.
- Find and display the count of the weak primes below 1,000,000.
- Find and display the count of the weak primes below 10,000,000.
- (Optional) display the counts and "below numbers" with commas.
Show all output here.
- Related Task
- Also see
-
- The OEIS article A051634: strong primes.
- The OEIS article A051635: weak primes.
ALGOL 68
<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 may 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>
- Output:
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
C
<lang c>#include <stdbool.h>
- include <stdint.h>
- include <stdio.h>
- include <stdlib.h>
const int PRIMES[] = {
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, 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, 1229, 1231, 1237, 1249, 1259, 1277, 1279, 1283, 1289, 1291, 1297, 1301, 1303, 1307, 1319, 1321, 1327, 1361, 1367, 1373, 1381, 1399, 1409, 1423, 1427, 1429, 1433, 1439, 1447, 1451, 1453, 1459, 1471, 1481, 1483, 1487, 1489, 1493, 1499, 1511, 1523, 1531, 1543, 1549, 1553, 1559, 1567, 1571, 1579, 1583, 1597, 1601, 1607, 1609, 1613, 1619, 1621, 1627, 1637, 1657, 1663, 1667, 1669, 1693, 1697, 1699, 1709, 1721, 1723, 1733, 1741, 1747, 1753, 1759, 1777, 1783, 1787, 1789, 1801, 1811, 1823, 1831, 1847, 1861, 1867, 1871, 1873, 1877, 1879, 1889, 1901, 1907, 1913, 1931, 1933, 1949, 1951, 1973, 1979, 1987, 1993, 1997, 1999, 2003, 2011, 2017, 2027, 2029, 2039, 2053, 2063, 2069, 2081, 2083, 2087, 2089, 2099, 2111, 2113, 2129, 2131, 2137, 2141, 2143, 2153, 2161, 2179, 2203, 2207, 2213, 2221, 2237, 2239, 2243, 2251, 2267, 2269, 2273, 2281, 2287, 2293, 2297, 2309, 2311, 2333, 2339, 2341, 2347, 2351, 2357, 2371, 2377, 2381, 2383, 2389, 2393, 2399, 2411, 2417, 2423, 2437, 2441, 2447, 2459, 2467, 2473, 2477, 2503, 2521, 2531, 2539, 2543, 2549, 2551, 2557, 2579, 2591, 2593, 2609, 2617, 2621, 2633, 2647, 2657, 2659, 2663, 2671, 2677, 2683, 2687, 2689, 2693, 2699, 2707, 2711, 2713, 2719, 2729, 2731, 2741, 2749, 2753, 2767, 2777, 2789, 2791, 2797, 2801, 2803, 2819, 2833, 2837, 2843, 2851, 2857, 2861, 2879, 2887, 2897, 2903, 2909, 2917, 2927, 2939, 2953, 2957, 2963, 2969, 2971, 2999, 3001, 3011, 3019, 3023, 3037, 3041, 3049, 3061, 3067, 3079, 3083, 3089, 3109, 3119, 3121, 3137, 3163
};
- define PRIME_LENGTH (sizeof(PRIMES) / sizeof(int))
bool isPrime(int n) {
int i;
if (n < 2) { return false; }
for (i = 0; i < PRIME_LENGTH; ++i) { if (n == PRIMES[i]) { return true; } if (n % PRIMES[i] == 0) { return false; } if (n < PRIMES[i] * PRIMES[i]) { break; } }
return true;
}
int main() {
const int MAX_LENGTH = 700000; int i, n, c1, c2;
int *primePtr = calloc(MAX_LENGTH, sizeof(int)); if (primePtr == 0) { return EXIT_FAILURE; }
for (i = 0; i < PRIME_LENGTH; i++) { primePtr[i] = PRIMES[i]; }
i--; for (n = PRIMES[i] + 4; n < 10000100;) { if (isPrime(n)) { primePtr[i++] = n; } n += 2;
if (isPrime(n)) { primePtr[i++] = n; } n += 4;
if (i >= MAX_LENGTH) { printf("Allocate more memory."); return EXIT_FAILURE; } }
///////////////////////////////////////////////////////////// printf("First 36 strong primes:"); c1 = 0; c2 = 0; for (n = 0, i = 1; i < MAX_LENGTH - 1; i++) { if (2 * primePtr[i] > primePtr[i - 1] + primePtr[i + 1]) { if (n < 36) { printf(" %d", primePtr[i]); n++; } if (primePtr[i] < 1000000) { c1++; c2++; } else if (primePtr[i] < 10000000) { c2++; } else break; } } printf("\nThere are %d strong primes below 1,000,000", c1); printf("\nThere are %d strong primes below 10,000,000\n\n", c2);
///////////////////////////////////////////////////////////// printf("First 37 weak primes:"); c1 = 0; c2 = 0; for (n = 0, i = 1; i < MAX_LENGTH - 1; i++) { if (2 * primePtr[i] < primePtr[i - 1] + primePtr[i + 1]) { if (n < 37) { printf(" %d", primePtr[i]); n++; } if (primePtr[i] < 1000000) { c1++; c2++; } else if (primePtr[i] < 10000000) { c2++; } else break; } } printf("\nThere are %d weak primes below 1,000,000", c1); printf("\nThere are %d weak primes below 10,000,000\n\n", c2);
free(primePtr); return EXIT_SUCCESS;
}</lang>
- Output:
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 There are 37722 strong primes below 1,000,000 There are 320990 strong primes below 10,000,000 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 There are 37780 weak primes below 1,000,000 There are 321750 weak primes below 10,000,000
C#
<lang csharp>using static System.Console; using static System.Linq.Enumerable; using System;
public static class StrongAndWeakPrimes {
public static void Main() { var primes = PrimeGenerator(10_000_100).ToList(); var strongPrimes = from i in Range(1, primes.Count - 2) where primes[i] > (primes[i-1] + primes[i+1]) / 2 select primes[i]; var weakPrimes = from i in Range(1, primes.Count - 2) where primes[i] < (primes[i-1] + primes[i+1]) / 2.0 select primes[i]; WriteLine($"First 36 strong primes: {string.Join(", ", strongPrimes.Take(36))}"); WriteLine($"There are {strongPrimes.TakeWhile(p => p < 1_000_000).Count():N0} strong primes below {1_000_000:N0}"); WriteLine($"There are {strongPrimes.TakeWhile(p => p < 10_000_000).Count():N0} strong primes below {10_000_000:N0}"); WriteLine($"First 37 weak primes: {string.Join(", ", weakPrimes.Take(37))}"); WriteLine($"There are {weakPrimes.TakeWhile(p => p < 1_000_000).Count():N0} weak primes below {1_000_000:N0}"); WriteLine($"There are {weakPrimes.TakeWhile(p => p < 10_000_000).Count():N0} weak primes below {1_000_000:N0}"); }
}</lang>
- Output:
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 There are 37,723 strong primes below 1,000,000 There are 320,991 strong primes below 10,000,000 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 There are 37,780 weak primes below 1,000,000 There are 321,750 weak primes below 1,000,000
C++
<lang cpp>#include <algorithm>
- include <iostream>
- include <iterator>
- include <locale>
- include <vector>
- include "prime_sieve.hpp"
const int limit1 = 1000000; const int limit2 = 10000000;
class prime_info { public:
explicit prime_info(int max) : max_print(max) {} void add_prime(int prime); void print(std::ostream& os, const char* name) const;
private:
int max_print; int count1 = 0; int count2 = 0; std::vector<int> primes;
};
void prime_info::add_prime(int prime) {
++count2; if (prime < limit1) ++count1; if (count2 <= max_print) primes.push_back(prime);
}
void prime_info::print(std::ostream& os, const char* name) const {
os << "First " << max_print << " " << name << " primes: "; std::copy(primes.begin(), primes.end(), std::ostream_iterator<int>(os, " ")); os << '\n'; os << "Number of " << name << " primes below " << limit1 << ": " << count1 << '\n'; os << "Number of " << name << " primes below " << limit2 << ": " << count2 << '\n';
}
int main() {
prime_sieve sieve(limit2 + 100);
// write numbers with groups of digits separated according to the system default locale std::cout.imbue(std::locale(""));
// count and print strong/weak prime numbers prime_info strong_primes(36); prime_info weak_primes(37); int p1 = 2, p2 = 3; for (int p3 = 5; p2 < limit2; ++p3) { if (!sieve.is_prime(p3)) continue; int diff = p1 + p3 - 2 * p2; if (diff < 0) strong_primes.add_prime(p2); else if (diff > 0) weak_primes.add_prime(p2); p1 = p2; p2 = p3; } strong_primes.print(std::cout, "strong"); weak_primes.print(std::cout, "weak"); return 0;
}</lang>
Contents of prime_sieve.hpp: <lang cpp>#ifndef PRIME_SIEVE_HPP
- define PRIME_SIEVE_HPP
- include <algorithm>
- include <vector>
/**
* A simple implementation of the Sieve of Eratosthenes. * See https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes. */
class prime_sieve { public:
explicit prime_sieve(size_t); bool is_prime(size_t) const;
private:
std::vector<bool> is_prime_;
};
/**
* Constructs a sieve with the given limit. * * @param limit the maximum integer that can be tested for primality */
inline prime_sieve::prime_sieve(size_t limit) {
limit = std::max(size_t(3), limit); is_prime_.resize(limit/2, true); for (size_t p = 3; p * p <= limit; p += 2) { if (is_prime_[p/2 - 1]) { size_t inc = 2 * p; for (size_t q = p * p; q <= limit; q += inc) is_prime_[q/2 - 1] = false; } }
}
/**
* Returns true if the given integer is a prime number. The integer * must be less than or equal to the limit passed to the constructor. * * @param n an integer less than or equal to the limit passed to the * constructor * @return true if the integer is prime */
inline bool prime_sieve::is_prime(size_t n) const {
if (n == 2) return true; if (n < 2 || n % 2 == 0) return false; return is_prime_.at(n/2 - 1);
}
- endif</lang>
- Output:
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 Number of strong primes below 1,000,000: 37,723 Number of 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 Number of weak primes below 1,000,000: 37,780 Number of weak primes below 10,000,000: 321,750
D
<lang d>import std.algorithm; import std.array; import std.range; import std.stdio;
immutable PRIMES = [
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, 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, 1229, 1231, 1237, 1249, 1259, 1277, 1279, 1283, 1289, 1291, 1297, 1301, 1303, 1307, 1319, 1321, 1327, 1361, 1367, 1373, 1381, 1399, 1409, 1423, 1427, 1429, 1433, 1439, 1447, 1451, 1453, 1459, 1471, 1481, 1483, 1487, 1489, 1493, 1499, 1511, 1523, 1531, 1543, 1549, 1553, 1559, 1567, 1571, 1579, 1583, 1597, 1601, 1607, 1609, 1613, 1619, 1621, 1627, 1637, 1657, 1663, 1667, 1669, 1693, 1697, 1699, 1709, 1721, 1723, 1733, 1741, 1747, 1753, 1759, 1777, 1783, 1787, 1789, 1801, 1811, 1823, 1831, 1847, 1861, 1867, 1871, 1873, 1877, 1879, 1889, 1901, 1907, 1913, 1931, 1933, 1949, 1951, 1973, 1979, 1987, 1993, 1997, 1999, 2003, 2011, 2017, 2027, 2029, 2039, 2053, 2063, 2069, 2081, 2083, 2087, 2089, 2099, 2111, 2113, 2129, 2131, 2137, 2141, 2143, 2153, 2161, 2179, 2203, 2207, 2213, 2221, 2237, 2239, 2243, 2251, 2267, 2269, 2273, 2281, 2287, 2293, 2297, 2309, 2311, 2333, 2339, 2341, 2347, 2351, 2357, 2371, 2377, 2381, 2383, 2389, 2393, 2399, 2411, 2417, 2423, 2437, 2441, 2447, 2459, 2467, 2473, 2477, 2503, 2521, 2531, 2539, 2543, 2549, 2551, 2557, 2579, 2591, 2593, 2609, 2617, 2621, 2633, 2647, 2657, 2659, 2663, 2671, 2677, 2683, 2687, 2689, 2693, 2699, 2707, 2711, 2713, 2719, 2729, 2731, 2741, 2749, 2753, 2767, 2777, 2789, 2791, 2797, 2801, 2803, 2819, 2833, 2837, 2843, 2851, 2857, 2861, 2879, 2887, 2897, 2903, 2909, 2917, 2927, 2939, 2953, 2957, 2963, 2969, 2971, 2999, 3001, 3011, 3019, 3023, 3037, 3041, 3049, 3061, 3067, 3079, 3083, 3089, 3109, 3119, 3121, 3137, 3163, 3167, 3169, 3181, 3187, 3191, 3203, 3209, 3217, 3221, 3229, 3251, 3253, 3257, 3259, 3271, 3299, 3301, 3307, 3313, 3319, 3323, 3329, 3331, 3343, 3347, 3359, 3361, 3371, 3373, 3389, 3391, 3407, 3413, 3433, 3449, 3457, 3461, 3463, 3467, 3469, 3491, 3499, 3511, 3517, 3527, 3529, 3533, 3539, 3541, 3547, 3557, 3559, 3571, 3581, 3583, 3593, 3607, 3613, 3617, 3623, 3631, 3637, 3643, 3659, 3671, 3673, 3677, 3691, 3697, 3701, 3709, 3719, 3727, 3733, 3739, 3761, 3767, 3769, 3779, 3793, 3797, 3803, 3821, 3823, 3833, 3847, 3851, 3853, 3863, 3877, 3881, 3889, 3907, 3911, 3917, 3919, 3923, 3929, 3931, 3943, 3947, 3967, 3989, 4001, 4003, 4007, 4013, 4019, 4021, 4027, 4049, 4051, 4057, 4073, 4079, 4091, 4093, 4099, 4111, 4127, 4129, 4133, 4139, 4153, 4157, 4159, 4177, 4201, 4211, 4217, 4219, 4229, 4231, 4241, 4243, 4253, 4259, 4261, 4271, 4273, 4283, 4289, 4297, 4327, 4337, 4339, 4349, 4357, 4363, 4373, 4391, 4397, 4409, 4421, 4423, 4441, 4447, 4451, 4457, 4463, 4481, 4483, 4493, 4507, 4513, 4517, 4519, 4523, 4547, 4549, 4561, 4567, 4583, 4591, 4597, 4603, 4621, 4637, 4639, 4643, 4649, 4651, 4657, 4663, 4673, 4679, 4691, 4703, 4721, 4723, 4729, 4733, 4751, 4759, 4783, 4787, 4789, 4793, 4799, 4801, 4813, 4817, 4831, 4861, 4871, 4877, 4889, 4903, 4909, 4919, 4931, 4933, 4937, 4943, 4951, 4957, 4967, 4969, 4973, 4987, 4993, 4999, 5003, 5009, 5011, 5021, 5023, 5039, 5051, 5059, 5077, 5081, 5087, 5099, 5101, 5107, 5113, 5119, 5147, 5153, 5167, 5171, 5179, 5189, 5197, 5209, 5227, 5231, 5233, 5237, 5261, 5273, 5279, 5281, 5297, 5303, 5309, 5323, 5333, 5347, 5351, 5381, 5387, 5393, 5399, 5407, 5413, 5417, 5419, 5431, 5437, 5441, 5443, 5449, 5471, 5477, 5479, 5483, 5501, 5503, 5507, 5519, 5521, 5527, 5531, 5557, 5563, 5569, 5573, 5581, 5591, 5623, 5639, 5641, 5647, 5651, 5653, 5657, 5659, 5669, 5683, 5689, 5693, 5701, 5711, 5717, 5737, 5741, 5743, 5749, 5779, 5783, 5791, 5801, 5807, 5813, 5821, 5827, 5839, 5843, 5849, 5851, 5857, 5861, 5867, 5869, 5879, 5881, 5897, 5903, 5923, 5927, 5939, 5953, 5981, 5987, 6007, 6011, 6029, 6037, 6043, 6047, 6053, 6067, 6073, 6079, 6089, 6091, 6101, 6113, 6121, 6131, 6133, 6143, 6151, 6163, 6173, 6197, 6199, 6203, 6211, 6217, 6221, 6229, 6247, 6257, 6263, 6269, 6271, 6277, 6287, 6299, 6301, 6311, 6317, 6323, 6329, 6337, 6343, 6353, 6359, 6361, 6367, 6373, 6379, 6389, 6397, 6421, 6427, 6449, 6451, 6469, 6473, 6481, 6491, 6521, 6529, 6547, 6551, 6553, 6563, 6569, 6571, 6577, 6581, 6599, 6607, 6619, 6637, 6653, 6659, 6661, 6673, 6679, 6689, 6691, 6701, 6703, 6709, 6719, 6733, 6737, 6761, 6763, 6779, 6781, 6791, 6793, 6803, 6823, 6827, 6829, 6833, 6841, 6857, 6863, 6869, 6871, 6883, 6899, 6907, 6911, 6917, 6947, 6949, 6959, 6961, 6967, 6971, 6977, 6983, 6991, 6997, 7001, 7013, 7019, 7027, 7039, 7043, 7057, 7069, 7079, 7103, 7109, 7121, 7127, 7129, 7151, 7159, 7177, 7187, 7193, 7207, 7211, 7213, 7219, 7229, 7237, 7243, 7247, 7253, 7283, 7297, 7307, 7309, 7321, 7331, 7333, 7349, 7351, 7369, 7393, 7411, 7417, 7433, 7451, 7457, 7459, 7477, 7481, 7487, 7489, 7499, 7507, 7517, 7523, 7529, 7537, 7541, 7547, 7549, 7559, 7561, 7573, 7577, 7583, 7589, 7591, 7603, 7607, 7621, 7639, 7643, 7649, 7669, 7673, 7681, 7687, 7691, 7699, 7703, 7717, 7723, 7727, 7741, 7753, 7757, 7759, 7789, 7793, 7817, 7823, 7829, 7841, 7853, 7867, 7873, 7877, 7879, 7883, 7901, 7907, 7919, 7927, 7933, 7937, 7949, 7951, 7963, 7993, 8009, 8011, 8017, 8039, 8053, 8059, 8069, 8081, 8087, 8089, 8093, 8101, 8111, 8117, 8123, 8147, 8161, 8167, 8171, 8179, 8191, 8209, 8219, 8221, 8231, 8233, 8237, 8243, 8263, 8269, 8273, 8287, 8291, 8293, 8297, 8311, 8317, 8329, 8353, 8363, 8369, 8377, 8387, 8389, 8419, 8423, 8429, 8431, 8443, 8447, 8461, 8467, 8501, 8513, 8521, 8527, 8537, 8539, 8543, 8563, 8573, 8581, 8597, 8599, 8609, 8623, 8627, 8629, 8641, 8647, 8663, 8669, 8677, 8681, 8689, 8693, 8699, 8707, 8713, 8719, 8731, 8737, 8741, 8747, 8753, 8761, 8779, 8783, 8803, 8807, 8819, 8821, 8831, 8837, 8839, 8849, 8861, 8863, 8867, 8887, 8893, 8923, 8929, 8933, 8941, 8951, 8963, 8969, 8971, 8999, 9001, 9007, 9011, 9013, 9029, 9041, 9043, 9049, 9059, 9067, 9091, 9103, 9109, 9127, 9133, 9137, 9151, 9157, 9161, 9173, 9181, 9187, 9199, 9203, 9209, 9221, 9227, 9239, 9241, 9257, 9277, 9281, 9283, 9293, 9311, 9319, 9323, 9337, 9341, 9343, 9349, 9371, 9377, 9391, 9397, 9403, 9413, 9419, 9421, 9431, 9433, 9437, 9439, 9461, 9463, 9467, 9473, 9479, 9491, 9497, 9511, 9521, 9533, 9539, 9547, 9551, 9587, 9601, 9613, 9619, 9623, 9629, 9631, 9643, 9649, 9661, 9677, 9679, 9689, 9697, 9719, 9721, 9733, 9739, 9743, 9749, 9767, 9769, 9781, 9787, 9791, 9803, 9811, 9817, 9829, 9833, 9839, 9851, 9857, 9859, 9871, 9883, 9887, 9901, 9907, 9923, 9929, 9931, 9941, 9949, 9967, 9973,
];
bool isPrime(int n) {
if (n < 2) { return false; }
foreach (prime; PRIMES) { if (n == prime) { return true; } if (n % prime == 0) { return false; } if (n < prime * prime) { if (n > PRIMES[$-1] * PRIMES[$-1]) { assert(false, "Out of pre-computed primes."); } break; } }
return true;
}
void main() {
auto primeList = iota(2, 10_000_100).filter!isPrime.array;
int[] strongPrimes, weakPrimes; foreach (i,p; primeList) { if (i > 0 && i < primeList.length - 1) { if (p > 0.5 * (primeList[i - 1] + primeList[i + 1])) { strongPrimes ~= p; } else if (p < 0.5 * (primeList[i - 1] + primeList[i + 1])) { weakPrimes ~= p; } } }
writeln("First 36 strong primes: ", strongPrimes[0..36]); writefln("There are %d strong primes below 1,000,000", strongPrimes.filter!"a<1_000_000".count); writefln("There are %d strong primes below 10,000,000", strongPrimes.filter!"a<10_000_000".count);
writeln("First 37 weak primes: ", weakPrimes[0..37]); writefln("There are %d weak primes below 1,000,000", weakPrimes.filter!"a<1_000_000".count); writefln("There are %d weak primes below 10,000,000", weakPrimes.filter!"a<10_000_000".count);
}</lang>
- Output:
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] There are 37723 strong primes below 1,000,000 There are 320991 strong primes below 10,000,000 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] There are 37780 weak primes below 1,000,000 There are 321750 weak primes below 10,000,000
Factor
<lang factor>USING: formatting grouping kernel math math.primes sequences tools.memory.private ; IN: rosetta-code.strong-primes
- fn ( p-1 p p+1 -- p sum ) rot + 2 / ;
- strong? ( p-1 p p+1 -- ? ) fn > ;
- weak? ( p-1 p p+1 -- ? ) fn < ;
- swprimes ( seq quot -- seq )
[ 3 <clumps> ] dip [ first3 ] prepose filter [ second ] map ; inline
- stats ( seq n -- firstn count1 count2 )
[ head ] [ drop [ 1e6 < ] filter length ] [ drop length ] 2tri [ commas ] bi@ ;
10,000,019 primes-upto [ strong? ] over [ weak? ] [ swprimes ] 2bi@ [ 36 ] [ 37 ] bi* [ stats ] 2bi@
"First 36 strong primes:\n%[%d, %] %s strong primes below 1,000,000 %s strong primes below 10,000,000\n First 37 weak primes:\n%[%d, %] %s weak primes below 1,000,000 %s weak primes below 10,000,000\n" printf</lang>
- Output:
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 } 37,723 strong primes below 1,000,000 320,991 strong primes below 10,000,000 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 } 37,780 weak primes below 1,000,000 321,750 weak primes below 10,000,000
Frink
<lang frink> strongPrimes[end=undef] := select[primes[3,end], {|p| p > (previousPrime[p] + nextPrime[p])/2 }] weakPrimes[end=undef] := select[primes[3,end], {|p| p < (previousPrime[p] + nextPrime[p])/2 }]
println["First 36 strong primes: " + first[strongPrimes[], 36]] println["Strong primes below 1,000,000: " + length[strongPrimes[1_000_000]]] println["Strong primes below 10,000,000: " + length[strongPrimes[10_000_000]]]
println["First 37 weak primes: " + first[weakPrimes[], 37]] println["Weak primes below 1,000,000: " + length[weakPrimes[1_000_000]]] println["Weak primes below 10,000,000: " + length[weakPrimes[10_000_000]]] </lang>
- Output:
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: 37723 Strong primes below 10,000,000: 320991 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: 37780 Weak primes below 10,000,000: 321750
Go
<lang go>package main
import "fmt"
func sieve(limit int) []bool {
limit++ // True denotes composite, false denotes prime. // Don't bother marking even numbers >= 4 as composite. c := make([]bool, limit) c[0] = true c[1] = true
p := 3 // start from 3 for { p2 := p * p if p2 >= limit { break } for i := p2; i < limit; i += 2 * p { c[i] = true } for { p += 2 if !c[p] { break } } } return c
}
func commatize(n int) string {
s := fmt.Sprintf("%d", n) le := len(s) for i := le - 3; i >= 1; i -= 3 { s = s[0:i] + "," + s[i:] } return s
}
func main() {
// sieve up to 10,000,019 - the first prime after 10 million const limit = 1e7 + 19 sieved := sieve(limit) // extract primes var primes = []int{2} for i := 3; i <= limit; i += 2 { if !sieved[i] { primes = append(primes, i) } } // extract strong and weak primes var strong []int var weak = []int{3} // so can use integer division for rest for i := 2; i < len(primes)-1; i++ { // start from 5 if primes[i] > (primes[i-1]+primes[i+1])/2 { strong = append(strong, primes[i]) } else if primes[i] < (primes[i-1]+primes[i+1])/2 { weak = append(weak, primes[i]) } }
fmt.Println("The first 36 strong primes are:") fmt.Println(strong[:36]) count := 0 for _, p := range strong { if p >= 1e6 { break } count++ } fmt.Println("\nThe number of strong primes below 1,000,000 is", commatize(count)) fmt.Println("\nThe number of strong primes below 10,000,000 is", commatize(len(strong)))
fmt.Println("\nThe first 37 weak primes are:") fmt.Println(weak[:37]) count = 0 for _, p := range weak { if p >= 1e6 { break } count++ } fmt.Println("\nThe number of weak primes below 1,000,000 is", commatize(count)) fmt.Println("\nThe number of weak primes below 10,000,000 is", commatize(len(weak)))
}</lang>
- Output:
The first 36 strong primes are: [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] The number of strong primes below 1,000,000 is 37,723 The number of strong primes below 10,000,000 is 320,991 The first 37 weak primes are: [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] The number of weak primes below 1,000,000 is 37,780 The number of weak primes below 10,000,000 is 321,750
Haskell
Uses primes library: http://hackage.haskell.org/package/primes-0.2.1.0/docs/Data-Numbers-Primes.html <lang haskell>import Text.Printf (printf) import Data.Numbers.Primes (primes)
xPrimes :: (Real a, Fractional b) => (b -> b -> Bool) -> [a] -> [a] xPrimes op ps@(p1:p2:p3:xs)
| realToFrac p2 `op` (realToFrac (p1 + p3) / 2) = p2 : xPrimes op (tail ps) | otherwise = xPrimes op (tail ps)
main :: IO () main = do
printf "First 36 strong primes: %s\n" . show . take 36 $ strongPrimes printf "Strong primes below 1,000,000: %d\n" . length . takeWhile (<1000000) $ strongPrimes printf "Strong primes below 10,000,000: %d\n\n" . length . takeWhile (<10000000) $ strongPrimes
printf "First 37 weak primes: %s\n" . show . take 37 $ weakPrimes printf "Weak primes below 1,000,000: %d\n" . length . takeWhile (<1000000) $ weakPrimes printf "Weak primes below 10,000,000: %d\n\n" . length . takeWhile (<10000000) $ weakPrimes where strongPrimes = xPrimes (>) primes weakPrimes = xPrimes (<) primes</lang>
- Output:
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: 37723 Strong primes below 10,000,000: 320991 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: 37780 Weak primes below 10,000,000: 321750
J
Filter =: (#~`)(`:6) average =: +/ % # NB. vector of primes from 2 to 10000019 PRIMES=:i.@>:&.(p:inv) 10000000 strongQ =: 1&{ > [: average {. , {: STRONG_PRIMES=: (0, 0,~ 3&(strongQ\))Filter PRIMES NB. first 36 strong primes 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 NB. tally of strong primes less than one and ten million +/ STRONG_PRIMES </ 1e6 * 1 10 37723 320991 weakQ =: 1&{ < [: average {. , {: weaklings =: (0, 0,~ 3&(weakQ\))Filter PRIMES NB. first 37 weak primes 37 {. weaklings 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 NB. tally of weak primes less than one and ten million +/ weaklings </ 1e6 * 1 10 37780 321750
Java
<lang java> public class StrongAndWeakPrimes {
private static int MAX = 10_000_000 + 1000; private static boolean[] primes = new boolean[MAX];
public static void main(String[] args) { sieve(); System.out.println("First 36 strong primes:"); displayStrongPrimes(36); for ( int n : new int[] {1_000_000, 10_000_000}) { System.out.printf("Number of strong primes below %,d = %,d%n", n, strongPrimesBelow(n)); } System.out.println("First 37 weak primes:"); displayWeakPrimes(37); for ( int n : new int[] {1_000_000, 10_000_000}) { System.out.printf("Number of weak primes below %,d = %,d%n", n, weakPrimesBelow(n)); } }
private static int weakPrimesBelow(int maxPrime) { int priorPrime = 2; int currentPrime = 3; int count = 0; while ( currentPrime < maxPrime ) { int nextPrime = getNextPrime(currentPrime); if ( currentPrime * 2 < priorPrime + nextPrime ) { count++; } priorPrime = currentPrime; currentPrime = nextPrime; } return count; }
private static void displayWeakPrimes(int maxCount) { int priorPrime = 2; int currentPrime = 3; int count = 0; while ( count < maxCount ) { int nextPrime = getNextPrime(currentPrime); if ( currentPrime * 2 < priorPrime + nextPrime) { count++; System.out.printf("%d ", currentPrime); } priorPrime = currentPrime; currentPrime = nextPrime; } System.out.println(); }
private static int getNextPrime(int currentPrime) { int nextPrime = currentPrime + 2; while ( ! primes[nextPrime] ) { nextPrime += 2; } return nextPrime; } private static int strongPrimesBelow(int maxPrime) { int priorPrime = 2; int currentPrime = 3; int count = 0; while ( currentPrime < maxPrime ) { int nextPrime = getNextPrime(currentPrime); if ( currentPrime * 2 > priorPrime + nextPrime ) { count++; } priorPrime = currentPrime; currentPrime = nextPrime; } return count; } private static void displayStrongPrimes(int maxCount) { int priorPrime = 2; int currentPrime = 3; int count = 0; while ( count < maxCount ) { int nextPrime = getNextPrime(currentPrime); if ( currentPrime * 2 > priorPrime + nextPrime) { count++; System.out.printf("%d ", currentPrime); } priorPrime = currentPrime; currentPrime = nextPrime; } System.out.println(); }
private static final void sieve() { // primes for ( int i = 2 ; i < MAX ; i++ ) { primes[i] = true; } for ( int i = 2 ; i < MAX ; i++ ) { if ( primes[i] ) { for ( int j = 2*i ; j < MAX ; j += i ) { primes[j] = false; } } } }
} </lang>
- Output:
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 Number of strong primes below 1,000,000 = 37,723 Number of 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 Number of weak primes below 1,000,000 = 37,780 Number of weak primes below 10,000,000 = 321,750
Julia
<lang julia>using Primes, Formatting
function parseprimelist()
primelist = primes(2, 10000019) strongs = Vector{Int64}() weaks = Vector{Int64}() balanceds = Vector{Int64}() for (n, p) in enumerate(primelist) if n == 1 || n == length(primelist) continue end x = (primelist[n - 1] + primelist[n + 1]) / 2 if x > p push!(weaks, p) elseif x < p push!(strongs, p) else push!(balanceds, p) end end println("The first 36 strong primes are: ", strongs[1:36]) println("There are ", format(sum(map(x -> x < 1000000, strongs)), commas=true), " stromg primes less than 1 million.") println("There are ", format(length(strongs), commas=true), " strong primes less than 10 million.") println("The first 37 weak primes are: ", weaks[1:37]) println("There are ", format(sum(map(x -> x < 1000000, weaks)), commas=true), " weak primes less than 1 million.") println("There are ", format(length(weaks), commas=true), " weak primes less than 10 million.") println("The first 28 balanced primes are: ", balanceds[1:28]) println("There are ", format(sum(map(x -> x < 1000000, balanceds)), commas=true), " balanced primes less than 1 million.") println("There are ", format(length(balanceds), commas=true), " balanced primes less than 10 million.")
end
parseprimelist()
</lang>
- Output:
The first 36 strong primes are: [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] There are 37,723 stromg primes less than 1 million. There are 320,991 strong primes less than 10 million. The first 37 weak primes are: [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] There are 37,780 weak primes less than 1 million. There are 321,750 weak primes less than 10 million. The first 28 balanced primes are: [5, 53, 157, 173, 211, 257, 263, 373, 563, 593, 607, 653, 733, 947, 977, 1103, 1123, 1187, 1223, 1367, 1511, 1747, 1753, 1907, 2287, 2417, 2677, 2903] There are 2,994 balanced primes less than 1 million. There are 21,837 balanced primes less than 10 million.
Kotlin
<lang scala>private const val MAX = 10000000 + 1000 private val primes = BooleanArray(MAX)
fun main() {
sieve()
println("First 36 strong primes:") displayStrongPrimes(36) for (n in intArrayOf(1000000, 10000000)) { System.out.printf("Number of strong primes below %,d = %,d%n", n, strongPrimesBelow(n)) }
println("First 37 weak primes:") displayWeakPrimes(37) for (n in intArrayOf(1000000, 10000000)) { System.out.printf("Number of weak primes below %,d = %,d%n", n, weakPrimesBelow(n)) }
}
private fun weakPrimesBelow(maxPrime: Int): Int {
var priorPrime = 2 var currentPrime = 3 var count = 0 while (currentPrime < maxPrime) { val nextPrime = getNextPrime(currentPrime) if (currentPrime * 2 < priorPrime + nextPrime) { count++ } priorPrime = currentPrime currentPrime = nextPrime } return count
}
private fun displayWeakPrimes(maxCount: Int) {
var priorPrime = 2 var currentPrime = 3 var count = 0 while (count < maxCount) { val nextPrime = getNextPrime(currentPrime) if (currentPrime * 2 < priorPrime + nextPrime) { count++ print("$currentPrime ") } priorPrime = currentPrime currentPrime = nextPrime } println()
}
private fun getNextPrime(currentPrime: Int): Int {
var nextPrime = currentPrime + 2 while (!primes[nextPrime]) { nextPrime += 2 } return nextPrime
}
private fun strongPrimesBelow(maxPrime: Int): Int {
var priorPrime = 2 var currentPrime = 3 var count = 0 while (currentPrime < maxPrime) { val nextPrime = getNextPrime(currentPrime) if (currentPrime * 2 > priorPrime + nextPrime) { count++ } priorPrime = currentPrime currentPrime = nextPrime } return count
}
private fun displayStrongPrimes(maxCount: Int) {
var priorPrime = 2 var currentPrime = 3 var count = 0 while (count < maxCount) { val nextPrime = getNextPrime(currentPrime) if (currentPrime * 2 > priorPrime + nextPrime) { count++ print("$currentPrime ") } priorPrime = currentPrime currentPrime = nextPrime } println()
}
private fun sieve() { // primes
for (i in 2 until MAX) { primes[i] = true } for (i in 2 until MAX) { if (primes[i]) { var j = 2 * i while (j < MAX) { primes[j] = false j += i } } }
}</lang>
- Output:
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 Number of strong primes below 1,000,000 = 37,723 Number of 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 Number of weak primes below 1,000,000 = 37,780 Number of weak primes below 10,000,000 = 321,750
Lua
This could be made faster but favours readability. It runs in about 3.3 seconds in LuaJIT on a 2.8 GHz core. <lang lua>-- Return a table of the primes up to n, then one more function primeList (n)
local function isPrime (x) for d = 3, math.sqrt(x), 2 do if x % d == 0 then return false end end return true end local pTable, j = {2, 3} for i = 5, n, 2 do if isPrime(i) then table.insert(pTable, i) end j = i end repeat j = j + 2 until isPrime(j) table.insert(pTable, j) return pTable
end
-- Return a boolean indicating whether prime p is strong function isStrong (p)
if p == 1 or p == #prime then return false end return prime[p] > (prime[p-1] + prime[p+1]) / 2
end
-- Return a boolean indicating whether prime p is weak function isWeak (p)
if p == 1 or p == #prime then return false end return prime[p] < (prime[p-1] + prime[p+1]) / 2
end
-- Main procedure prime = primeList(1e7) local strong, weak, sCount, wCount = {}, {}, 0, 0 for k, v in pairs(prime) do
if isStrong(k) then table.insert(strong, v) if v < 1e6 then sCount = sCount + 1 end end if isWeak(k) then table.insert(weak, v) if v < 1e6 then wCount = wCount + 1 end end
end print("The first 36 strong primes are:") for i = 1, 36 do io.write(strong[i] .. " ") end print("\n\nThere are " .. sCount .. " strong primes below one million.") print("\nThere are " .. #strong .. " strong primes below ten million.") print("\nThe first 37 weak primes are:") for i = 1, 37 do io.write(weak[i] .. " ") end print("\n\nThere are " .. wCount .. " weak primes below one million.") print("\nThere are " .. #weak .. " weak primes below ten million.")</lang>
- Output:
The first 36 strong primes are: 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 There are 37723 strong primes below one million. There are 320991 strong primes below ten million. The first 37 weak primes are: 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 There are 37780 weak primes below one million. There are 321750 weak primes below ten million.
Maple
<lang maple>isStrong := proc(n::posint) local holder; holder := false; if isprime(n) and 1/2*prevprime(n) + 1/2*nextprime(n) < n then
holder := true;
end if; return holder; end proc:
isWeak := proc(n::posint) local holder; holder := false; if isprime(n) and n < 1/2*prevprime(n) + 1/2*nextprime(n) then
holder := true;
end if; return holder; end proc
findStrong := proc(n::posint) local count, list, k; count := 0; list := []; for k from 3 while count < n do
if isStrong(k) then count := count + 1; list := [op(list), k]; end if;
end do; return list; end proc:
findWeak := proc(n::posint) local count, list, k; count := 0; list := []; for k from 3 while count < n do
if isWeak(k) then count := count + 1; list := [op(list), k]; end if;
end do; return list; end proc:
findStrong(36) findWeak(37) countStrong(1000000) countStrong(10000000) countWeak(1000000) countWeak(10000000)</lang>
- Output:
[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] [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] 37723 320991 37780 321750
Pascal
Converting the primes into deltaPrime, so that its easy to check the strong- /weakness. Startprime 2 +1 -> (3)+2-> (5)+2 ->(7) +4-> (11)+2 .... 1,2,2,4,2,4,2,4,6,2,.... By using only odd primes startprime is 3 and delta -> delta/2
If deltaAfter < deltaBefore than a strong prime is found. <lang pascal>program WeakPrim; {$IFNDEF FPC}
{$AppType CONSOLE}
{$ENDIF} const
PrimeLimit = 1000*1000*1000;//must be >= 2*3;
type
tLimit = 0..(PrimeLimit-1) DIV 2; tPrimCnt = 0..51*1000*1000; tWeakStrong = record strong, balanced, weak : NativeUint; end;
var
primes: array [tLimit] of byte; //always initialized with 0 at startup delta : array [tPrimCnt] of byte; cntWS : tWeakStrong; deltaCnt :NativeUint;
procedure sieveprimes; //Only odd numbers, minimal count of strikes var
spIdx,sieveprime,sievePos,fact :NativeUInt;
begin
spIdx := 1; repeat if primes[spIdx]=0 then begin sieveprime := 2*spIdx+1; fact := PrimeLimit DIV sieveprime; if Not(odd(fact)) then dec(fact); IF fact < sieveprime then BREAK; sievePos := ((fact*sieveprime)-1) DIV 2; fact := (fact-1) DIV 2; repeat primes[sievePos] := 1; repeat dec(fact); dec(sievePos,sieveprime); until primes[fact]= 0; until fact < spIdx; end; inc(spIdx); until false;
end; { Not neccessary for this small primes. procedure EmergencyStop(i:NativeInt); Begin
Writeln( 'STOP at ',i,'.th prime'); HALT(i);
end; } function GetDeltas:NativeUint; //Converting prime positions into distance var
i,j,last : NativeInt;
Begin
j :=0; i := 1; last :=1; For i := 1 to High(primes) do if primes[i] = 0 then Begin //IF i-last > 255 {aka delta prim > 512} then EmergencyStop (j); delta[j] := i-last; last := i; inc(j); end; GetDeltas := j;
end;
procedure OutHeader; Begin
writeln('Limit':12,'Strong':10,'balanced':12,'weak':10);
end;
procedure OutcntWS (const cntWS : tWeakStrong;Lmt:NativeInt); Begin
with cntWS do writeln(lmt:12,Strong:10,balanced:12,weak:10);
end;
procedure CntWeakStrong10(var Out:tWeakStrong); // Output a table of values for strang/balanced/weak for 10^n var
idx,diff,prime,lmt :NativeInt;
begin
OutHeader; lmt := 10; fillchar(Out,SizeOf(Out),#0); idx := 0; prime:=3; repeat dec(prime,2*delta[idx]); while idx < deltaCnt do Begin inc(prime,2*delta[idx]); IF prime > lmt then BREAK; diff := delta[idx] - delta[idx+1]; if diff>0 then inc(Out.strong) else if diff< 0 then inc(Out.weak) else inc(Out.balanced); inc(idx); end; OutcntWS(Out,Lmt); lmt := lmt*10; until Lmt > PrimeLimit;
end;
procedure WeakOut(cnt:NativeInt); var
idx,prime : NativeInt;
begin
Writeln('The first ',cnt,' weak primes'); prime:=3; idx := 0; repeat inc(prime,2*delta[idx]); if delta[idx] - delta[idx+1]< 0 then Begin write(prime,' '); dec(cnt); IF cnt <=0 then BREAK; end; inc(idx); until idx >= deltaCnt; Writeln;
end;
procedure StrongOut(cnt:NativeInt); var
idx,prime : NativeInt;
begin
Writeln('The first ',cnt,' strong primes'); prime:=3; idx := 0; repeat inc(prime,2*delta[idx]); if delta[idx] - delta[idx+1]> 0 then Begin write(prime,' '); dec(cnt); IF cnt <=0 then BREAK; end; inc(idx); until idx >= deltaCnt; Writeln;
end;
begin
sieveprimes; deltaCnt := GetDeltas; StrongOut(36); WeakOut(37); CntWeakStrong10(CntWs);
end.</lang>
- Output:
The 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 The 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 Limit Strong balanced weak 10 0 1 2 100 10 2 12 1000 73 15 79 10000 574 65 589 100000 4543 434 4614 1000000 37723 2994 37780 10000000 320991 21837 321750 100000000 2796946 167032 2797476 1000000000 24758535 1328401 24760597 real 0m3.011s
Perl
<lang perl>use ntheory qw(primes vecfirst);
sub comma {
(my $s = reverse shift) =~ s/(.{3})/$1,/g; $s =~ s/,(-?)$/$1/; $s = reverse $s;
}
sub below { my ($m, @a) = @_; vecfirst { $a[$_] > $m } 0..$#a }
my (@strong, @weak, @balanced); my @primes = @{ primes(10_000_019) };
for my $k (1 .. $#primes - 1) {
my $x = ($primes[$k - 1] + $primes[$k + 1]) / 2; if ($x > $primes[$k]) { push @weak, $primes[$k] } elsif ($x < $primes[$k]) { push @strong, $primes[$k] } else { push @balanced, $primes[$k] }
}
for ([\@strong, 'strong', 36, 1e6, 1e7],
[\@weak, 'weak', 37, 1e6, 1e7], [\@balanced, 'balanced', 28, 1e6, 1e7]) { my($pr, $type, $d, $c1, $c2) = @$_; print "\nFirst $d $type primes:\n", join ' ', map { comma $_ } @$pr[0..$d-1], "\n"; print "Count of $type primes <= @{[comma $c1]}: " . comma below($c1,@$pr) . "\n"; print "Count of $type primes <= @{[comma $c2]}: " . comma scalar @$pr . "\n";
}</lang>
- Output:
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 Count of strong primes <= 1,000,000: 37,723 Count of strong primes <= 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 Count of weak primes <= 1,000,000: 37,780 Count of weak primes <= 10,000,000: 321,750 First 28 balanced primes: 5 53 157 173 211 257 263 373 563 593 607 653 733 947 977 1,103 1,123 1,187 1,223 1,367 1,511 1,747 1,753 1,907 2,287 2,417 2,677 2,903 Count of balanced primes <= 1,000,000: 2,994 Count of balanced primes <= 10,000,000: 21,837
Phix
Using Extensible_prime_generator#Phix <lang Phix>while sieved<10_000_000 do add_block() end while sequence {strong, weak} @= {} for i=2 to abs(binary_search(10_000_000,primes))-1 do
integer p = primes[i], c = compare(p,(primes[i-1]+primes[i+1])/2) if c=+1 then strong &= p elsif c=-1 then weak &= p end if
end for printf(1,"The first 36 strong primes:") ?strong[1..36] printf(1,"The first 37 weak primes:") ?weak[1..37] printf(1,"%,7d strong primes below 1,000,000\n",abs(binary_search(1_000_000,strong))-1) printf(1,"%,7d strong primes below 10,000,000\n",length(strong)) printf(1,"%,7d weak primes below 1,000,000\n",abs(binary_search(1_000_000,weak))-1) printf(1,"%,7d weak primes below 10,000,000\n",length(weak))</lang>
- Output:
The 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} The 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} 37,723 strong primes below 1,000,000 320,991 strong primes below 10,000,000 37,780 weak primes below 1,000,000 321,750 weak primes below 10,000,000
PureBasic
<lang PureBasic>#MAX=10000000+20 Global Dim P.b(#MAX) : FillMemory(@P(),#MAX,1,#PB_Byte) Global NewList Primes.i() Global NewList Strong.i() Global NewList Weak.i()
For n=2 To Sqr(#MAX)+1 : If P(n) : m=n*n : While m<=#MAX : P(m)=0 : m+n : Wend : EndIf : Next For i=2 To #MAX : If p(i) : AddElement(Primes()) : Primes()=i : EndIf : Next
If FirstElement(Primes())
pp=Primes() While NextElement(Primes()) ap=Primes() If NextElement(Primes()) : np=Primes() : Else : Break : EndIf If ap>(pp+np)/2.0 : AddElement(Strong()) : Strong()=ap : If ap<1000000 : c1+1 : EndIf : EndIf If ap<(pp+np)/2.0 : AddElement(Weak()) : Weak()=ap : If ap<1000000 : c2+1 : EndIf : EndIf PreviousElement(Primes()) : pp=Primes() Wend
EndIf
OpenConsole() If FirstElement(Strong())
PrintN("First 36 strong primes:") Print(Str(Strong())+" ") For i=2 To 36 : If NextElement(Strong()) : Print(Str(Strong())+" ") : Else : Break : EndIf : Next PrintN("")
EndIf PrintN("Number of strong primes below 1'000'000 = "+FormatNumber(c1,0,".","'")) PrintN("Number of strong primes below 10'000'000 = "+FormatNumber(ListSize(Strong()),0,".","'")) If FirstElement(Weak())
PrintN("First 37 weak primes:") Print(Str(Weak())+" ") For i=2 To 37 : If NextElement(Weak()) : Print(Str(Weak())+" ") : Else : Break : EndIf : Next PrintN("")
EndIf PrintN("Number of weak primes below 1'000'000 = "+FormatNumber(c2,0,".","'")) PrintN("Number of weak primes below 10'000'000 = "+FormatNumber(ListSize(Weak()),0,".","'")) Input()</lang>
- Output:
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 Number of strong primes below 1'000'000 = 37'723 Number of 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 Number of weak primes below 1'000'000 = 37'780 Number of weak primes below 10'000'000 = 321'750
Python
Using the popular numpy library for fast prime generation.
COmputes and shows the requested output then adds similar output for the "balanced" case where prime(p) == [prime(p-1) + prime(p+1)] ÷ 2
.
<lang python>import numpy as np
def primesfrom2to(n):
# https://stackoverflow.com/questions/2068372/fastest-way-to-list-all-primes-below-n-in-python/3035188#3035188 """ Input n>=6, Returns a array of primes, 2 <= p < n """ sieve = np.ones(n//3 + (n%6==2), dtype=np.bool) sieve[0] = False for i in range(int(n**0.5)//3+1): if sieve[i]: k=3*i+1|1 sieve[ ((k*k)//3) ::2*k] = False sieve[(k*k+4*k-2*k*(i&1))//3::2*k] = False return np.r_[2,3,((3*np.nonzero(sieve)[0]+1)|1)]
p = primes10m = primesfrom2to(10_000_000) s = strong10m = [t for s, t, u in zip(p, p[1:], p[2:])
if t > (s + u) / 2]
w = weak10m = [t for s, t, u in zip(p, p[1:], p[2:])
if t < (s + u) / 2]
b = balanced10m = [t for s, t, u in zip(p, p[1:], p[2:])
if t == (s + u) / 2]
print('The first 36 strong primes:', s[:36]) print('The count of the strong primes below 1,000,000:',
sum(1 for p in s if p < 1_000_000))
print('The count of the strong primes below 10,000,000:', len(s)) print('\nThe first 37 weak primes:', w[:37]) print('The count of the weak primes below 1,000,000:',
sum(1 for p in w if p < 1_000_000))
print('The count of the weak primes below 10,000,000:', len(w)) print('\n\nThe first 10 balanced primes:', b[:10]) print('The count of balanced primes below 1,000,000:',
sum(1 for p in b if p < 1_000_000))
print('The count of balanced primes below 10,000,000:', len(b)) print('\nTOTAL primes below 1,000,000:',
sum(1 for pr in p if pr < 1_000_000))
print('TOTAL primes below 10,000,000:', len(p))</lang>
- Output:
The 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] The count of the strong primes below 1,000,000: 37723 The count of the strong primes below 10,000,000: 320991 The 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] The count of the weak primes below 1,000,000: 37780 The count of the weak primes below 10,000,000: 321749 The first 10 balanced primes: [5, 53, 157, 173, 211, 257, 263, 373, 563, 593] The count of balanced primes below 1,000,000: 2994 The count of balanced primes below 10,000,000: 21837 TOTAL primes below 1,000,000: 78498 TOTAL primes below 10,000,000: 664579
Raku
(formerly Perl 6)
<lang perl6>sub comma { $^i.flip.comb(3).join(',').flip }
use Math::Primesieve;
my $sieve = Math::Primesieve.new;
my @primes = $sieve.primes(10_000_019);
my (@weak, @balanced, @strong);
for 1 ..^ @primes - 1 -> $p {
given (@primes[$p - 1] + @primes[$p + 1]) / 2 { when * > @primes[$p] { @weak.push: @primes[$p] } when * < @primes[$p] { @strong.push: @primes[$p] } default { @balanced.push: @primes[$p] } }
}
for @strong, 'strong', 36,
@weak, 'weak', 37, @balanced, 'balanced', 28 -> @pr, $type, $d { say "\nFirst $d $type primes:\n", @pr[^$d]»., say "Count of $type primes <= {comma 1e6}: ", comma +@pr[^(@pr.first: * > 1e6,:k)]; say "Count of $type primes <= {comma 1e7}: ", comma +@pr;
}</lang>
- Output:
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) Count of strong primes <= 1,000,000: 37,723 Count of strong primes <= 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) Count of weak primes <= 1,000,000: 37,780 Count of weak primes <= 10,000,000: 321,750 First 28 balanced primes: (5 53 157 173 211 257 263 373 563 593 607 653 733 947 977 1,103 1,123 1,187 1,223 1,367 1,511 1,747 1,753 1,907 2,287 2,417 2,677 2,903) Count of balanced primes <= 1,000,000: 2,994 Count of balanced primes <= 10,000,000: 21,837
REXX
<lang rexx>/*REXX program lists a sequence (or a count) of ──strong── or ──weak── primes. */ parse arg N kind _ . 1 . okind; upper kind /*obtain optional arguments from the CL*/ if N== | N=="," then N= 36 /*Not specified? Then assume default.*/ if kind== | kind=="," then kind= 'STRONG' /* " " " " " */ if _\== then call ser 'too many arguments specified.' if kind\=='WEAK' & kind\=='STRONG' then call ser 'invalid 2nd argument: ' okind if kind =='WEAK' then weak= 1; else weak= 0 /*WEAK is a binary value for function.*/ w = linesize() - 1 /*obtain the usable width of the term. */ tell= (N>0); @.=; N= abs(N) /*N is negative? Then don't display. */ !.=0; !.1=2; !.2=3; !.3=5; !.4=7; !.5=11; !.6=13; !.7=17; !.8=19; !.9=23; #= 8 @.=; @.2=1; @.3=1; @.5=1; @.7=1; @.11=1; @.13=1; @.17=1; @.19=1; start= # + 1 m= 0; lim= 0 /*# is the number of low primes so far*/ $=; do i=3 for #-2 while lim<=N /* [↓] find primes, and maybe show 'em*/
call strongWeak i-1; $= strip($) /*go see if other part of a KIND prime.*/ end /*i*/ /* [↑] allows faster loop (below). */ /* [↓] N: default lists up to 35 #'s.*/ do j=!.#+2 by 2 while lim<N /*continue on with the next odd prime. */ if j // 3 == 0 then iterate /*is this integer a multiple of three? */ parse var j -1 _ /*obtain the last decimal digit of J */ if _ == 5 then iterate /*is this integer a multiple of five? */ if j // 7 == 0 then iterate /* " " " " " " seven? */ if j //11 == 0 then iterate /* " " " " " " eleven?*/ if j //13 == 0 then iterate /* " " " " " " 13 ? */ if j //17 == 0 then iterate /* " " " " " " 17 ? */ if j //19 == 0 then iterate /* " " " " " " 19 ? */ /* [↓] divide by the primes. ___ */ do k=start to # while !.k * !.k<=j /*divide J by other primes ≤ √ J */ if j // !.k ==0 then iterate j /*÷ by prev. prime? ¬prime ___ */ end /*k*/ /* [↑] only divide up to √ J */ #= # + 1 /*bump the count of number of primes. */ !.#= j; @.j= 1 /*define a prime and its index value.*/ call strongWeak #-1 /*go see if other part of a KIND prime.*/ end /*j*/ /* [↓] display number of primes found.*/
if $\== then say $ /*display any residual primes in $ list*/ say if tell then say commas(m)' ' kind "primes found."
else say commas(m)' ' kind "primes found below or equal to " commas(N).
exit /*stick a fork in it, we're all done. */ /*──────────────────────────────────────────────────────────────────────────────────────*/ add: m= m+1; lim= m; if \tell & y>N then do; lim= y; m= m-1; end; else call app; return 1 app: if tell then if length($ y)>w then do; say $; $= y; end; else $= $ y; return 1 ser: say; say; say '***error***' arg(1); say; say; exit 13 /*tell error message. */ commas: parse arg _; do jc=length(_)-3 to 1 by -3; _=insert(',', _, jc); end; return _ /*──────────────────────────────────────────────────────────────────────────────────────*/ strongWeak: parse arg x; Lp= x - 1; Hp= x + 1; y=!.x; s= (!.Lp + !.Hp) / 2
if weak then if ys then return add() /*is an strong prime.*/ return 0 /*not " " " */</lang>
This REXX program makes use of LINESIZE REXX program (or BIF) which is used to determine the screen width (or linesize) of the terminal (console). Some REXXes don't have this BIF.
The LINESIZE.REX REXX program is included here ───► LINESIZE.REX.
- output when using the default input of: 36 strong
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 36 STRONG primes found.
- output when using the default input of: -1000000 strong
37,723 STRONG primes found below or equal to 1,000,000.
- output when using the default input of: -10000000 strong
320,991 STRONG primes found below or equal to 10,000,000.
- output when using the default input of: 37 weak
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 37 WEAK primes found.
- output when using the default input of: -1000000 weak
37,780 WEAK primes found below or equal to 1,000,000.
- output when using the default input of: -10000000 weak
321,750 WEAK primes found below or equal to 10,000,000.
Ring
<lang ring> load "stdlib.ring"
see "working..." + nl
p = 0 num = 0 pr1 = 37 pr2 = 38 limit1 = 457 limit2 = 1000000 limit3 = 10000000 primes = []
see "first 36 strong primes:" + nl while true
p = p + 1 if isprime(p) if p < limit1 add(primes,p) else exit ok ok
end
ln = len(primes) for n = 2 to ln-1
tmp = (primes[n-1] + primes[n+1])/2 if primes[n] > tmp num = num + 1 if num < pr1 see " " + primes[n] ok ok
next
see nl + "first 37 weak primes:" + nl
num = 0 ln = len(primes) for n = 2 to ln-1
tmp = (primes[n-1] + primes[n+1])/2 if primes[n] < tmp num = num + 1 if num < pr2 see " " + primes[n] ok ok
next
p = 0 primes = [] while true
p = p + 1 if isprime(p) if p < limit3 add(primes,p) else exit ok ok
end
primes2 = 0 primes3 = 0 ln = len(primes) for n = 2 to ln-1
tmp = (primes[n-1] + primes[n+1])/2 if primes[n] > tmp if primes[n] < limit2 primes2 = primes2 + 1 ok if primes[n] < limit3 primes3 = primes3 + 1 else exit ok ok
next
see nl see "strong primes below 1,000,000: " + primes2 + nl see "strong primes below 10,000,000: " + primes3 + nl
primes2 = 0 primes3 = 0 ln = len(primes) for n = 2 to ln-1
tmp = (primes[n-1] + primes[n+1])/2 if primes[n] < tmp if primes[n] < limit2 primes2 = primes2 + 1 ok if primes[n] < limit3 primes3 = primes3 + 1 else exit ok ok
next
see nl see "weak primes below 1,000,000: " + primes2 + nl see "weak primes below 10,000,000: " + primes3 + nl </lang> Output:
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 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 strong primes below 1,000,000: 37723 strong primes below 10,000,000: 320991 weak primes below 1,000,000: 37780 weak primes below 10,000,000: 321750
Ruby
<lang ruby>require 'prime'
strong_gen = Enumerator.new{|y| Prime.each_cons(3){|a,b,c|y << b if a+c-b<b} } weak_gen = Enumerator.new{|y| Prime.each_cons(3){|a,b,c|y << b if a+c-b>b} }
puts "First 36 strong primes:" puts strong_gen.take(36).join(" "), "\n" puts "First 37 weak primes:" puts weak_gen.take(37).join(" "), "\n"
[1_000_000, 10_000_000].each do |limit|
strongs, weaks = 0, 0 Prime.each_cons(3) do |a,b,c| strongs += 1 if b > a+c-b weaks += 1 if b < a+c-b break if c > limit end puts "#{strongs} strong primes and #{weaks} weak primes below #{limit}."
end </lang>
- Output:
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 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 37723 strong primes and 37780 weak primes below 1000000. 320991 strong primes and 321750 weak primes below 10000000.
Scala
This example works entirely with lazily evaluated lists. It starts with a list of primes, and generates a sliding iterator that looks at each triplet of primes. Lists of strong and weak primes are built by applying the given filters then selecting the middle term from each triplet. <lang scala>object StrongWeakPrimes {
def main(args: Array[String]): Unit = { val bnd = 1000000 println( f"""|First 36 Strong Primes: ${strongPrimes.take(36).map(n => f"$n%,d").mkString(", ")} |Strong Primes < 1,000,000: ${strongPrimes.takeWhile(_ < bnd).size}%,d |Strong Primes < 10,000,000: ${strongPrimes.takeWhile(_ < 10*bnd).size}%,d | |First 37 Weak Primes: ${weakPrimes.take(37).map(n => f"$n%,d").mkString(", ")} |Weak Primes < 1,000,000: ${weakPrimes.takeWhile(_ < bnd).size}%,d |Weak Primes < 10,000,000: ${weakPrimes.takeWhile(_ < 10*bnd).size}%,d""".stripMargin) } def weakPrimes: LazyList[Int] = primeTrips.filter{case a +: b +: c +: _ => b < (a + c)/2.0}.map(_(1)).to(LazyList) def strongPrimes: LazyList[Int] = primeTrips.filter{case a +: b +: c +: _ => b > (a + c)/2}.map(_(1)).to(LazyList) def primeTrips: Iterator[LazyList[Int]] = primes.sliding(3) def primes: LazyList[Int] = 2 #:: LazyList.from(3, 2).filter(n => !Iterator.range(3, math.sqrt(n).toInt + 1, 2).exists(n%_ == 0))
}</lang>
- Output:
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 < 1,000,000: 37,723 Strong Primes < 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 < 1,000,000: 37,780 Weak Primes < 10,000,000: 321,750
Sidef
<lang ruby>var primes = 10_000_019.primes
var (*strong, *weak, *balanced)
for k in (1 ..^ primes.end) {
var p = primes[k]
given((primes[k-1] + primes[k+1])/2) { |x| case (x > p) { weak << p } case (x < p) { strong << p } else { balanced << p } }
}
for pr, type, d, c1, c2 in [
[ strong, 'strong', 36, 1e6, 1e7], [ weak, 'weak', 37, 1e6, 1e7], [balanced, 'balanced', 28, 1e6, 1e7],
] {
say ("\nFirst #{d} #{type} primes:\n", pr.first(d).map{.commify}.join(' ')) say ("Count of #{type} primes <= #{c1.commify}: ", pr.first_index { _ > 1e6 }.commify) say ("Count of #{type} primes <= #{c2.commify}: " , pr.len.commify)
}</lang>
- Output:
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 Count of strong primes <= 1,000,000: 37,723 Count of strong primes <= 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 Count of weak primes <= 1,000,000: 37,780 Count of weak primes <= 10,000,000: 321,750 First 28 balanced primes: 5 53 157 173 211 257 263 373 563 593 607 653 733 947 977 1,103 1,123 1,187 1,223 1,367 1,511 1,747 1,753 1,907 2,287 2,417 2,677 2,903 Count of balanced primes <= 1,000,000: 2,994 Count of balanced primes <= 10,000,000: 21,837
Swift
<lang swift>import Foundation
class PrimeSieve {
var composite: [Bool] init(size: Int) { composite = Array(repeating: false, count: size/2) var p = 3 while p * p <= size { if !composite[p/2 - 1] { let inc = p * 2 var q = p * p while q <= size { composite[q/2 - 1] = true q += inc } } p += 2 } } func isPrime(number: Int) -> Bool { if number < 2 { return false } if (number & 1) == 0 { return number == 2 } return !composite[number/2 - 1] }
}
func commatize(_ number: Int) -> String {
let n = NSNumber(value: number) return NumberFormatter.localizedString(from: n, number: .decimal)
}
let limit1 = 1000000 let limit2 = 10000000
class PrimeInfo {
let maxPrint: Int var count1: Int var count2: Int var primes: [Int] init(maxPrint: Int) { self.maxPrint = maxPrint count1 = 0 count2 = 0 primes = [] } func addPrime(prime: Int) { count2 += 1 if prime < limit1 { count1 += 1 } if count2 <= maxPrint { primes.append(prime) } } func printInfo(name: String) { print("First \(maxPrint) \(name) primes: \(primes)") print("Number of \(name) primes below \(commatize(limit1)): \(commatize(count1))") print("Number of \(name) primes below \(commatize(limit2)): \(commatize(count2))") }
}
var strongPrimes = PrimeInfo(maxPrint: 36) var weakPrimes = PrimeInfo(maxPrint: 37)
let sieve = PrimeSieve(size: limit2 + 100)
var p1 = 2, p2 = 3, p3 = 5 while p2 < limit2 {
if sieve.isPrime(number: p3) { let diff = p1 + p3 - 2 * p2 if diff < 0 { strongPrimes.addPrime(prime: p2) } else if diff > 0 { weakPrimes.addPrime(prime: p2) } p1 = p2 p2 = p3 } p3 += 2
}
strongPrimes.printInfo(name: "strong") weakPrimes.printInfo(name: "weak")</lang>
- Output:
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] Number of strong primes below 1,000,000: 37,723 Number of 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] Number of weak primes below 1,000,000: 37,780 Number of weak primes below 10,000,000: 321,750
Wren
<lang ecmascript>import "/math" for Int import "/fmt" for Fmt
var primes = Int.primeSieve(1e7 + 19) // next prime above 10 million var strong = [] var weak = [] for (p in 1...primes.count-1) {
if (primes[p] > (primes[p-1] + primes[p+1]) / 2) { strong.add(primes[p]) } else if (primes[p] < (primes[p-1] + primes[p+1]) / 2) { weak.add(primes[p]) }
}
System.print("The first 36 strong primes are:") Fmt.print("$d", strong.take(36)) Fmt.print("\nThe count of the strong primes below $,d is $,d.", 1e6, strong.count{ |n| n < 1e6 }) Fmt.print("\nThe count of the strong primes below $,d is $,d.", 1e7, strong.count{ |n| n < 1e7 })
System.print("\nThe first 37 weak primes are:") Fmt.print("$d", weak.take(37)) Fmt.print("\nThe count of the weak primes below $,d is $,d.", 1e6, weak.count{ |n| n < 1e6 }) Fmt.print("\nThe count of the weak primes below $,d is $,d.", 1e7, weak.count{ |n| n < 1e7 })</lang>
- Output:
The first 36 strong primes are: 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 The count of the strong primes below 1,000,000 is 37,723. The count of the strong primes below 10,000,000 is 320,991. The first 37 weak primes are: 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 The count of the weak primes below 1,000,000 is 37,780. The count of the weak primes below 10,000,000 is 321,750.
zkl
Using GMP (GNU Multiple Precision Arithmetic Library, probabilistic primes), because it is easy and fast to generate primes.
Extensible prime generator#zkl could be used instead. <lang zkl>var [const] BI=Import("zklBigNum"); // libGMP const N=1e7;
pw,strong,weak := BI(1),List(),List(); // 32,0991 32,1751 ps:=(3).pump(List,'wrap{ pw.nextPrime().toInt() }).copy(); // rolling window do{
pp,p,pn := ps; if((z:=(pp.toFloat() + pn)/2)){ // 2,3,5 --> 3.5 if(z>p) weak .append(p); else if(z<p) strong.append(p); } ps.pop(0); ps.append(pw.nextPrime().toInt());
}while(pn<=N);</lang> <lang zkl>foreach nm,list,psz in (T(T("strong",strong,36), T("weak",weak,37))){
println("First %d %s primes:\n%s".fmt(psz,nm,list[0,psz].concat(" "))); println("Count of %s primes <= %,10d: %,8d"
.fmt(nm,1e6,list.reduce('wrap(s,p){ s + (p<=1e6) },0)));
println("Count of %s primes <= %,10d: %,8d\n".fmt(nm,1e7,list.len()));
}</lang>
- Output:
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 Count of strong primes <= 1,000,000: 37,723 Count of strong primes <= 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 Count of weak primes <= 1,000,000: 37,780 Count of weak primes <= 10,000,000: 321,750