Strong and weak primes: Difference between revisions
Content added Content deleted
Line 546: | Line 546: | ||
+/ weaklings </ 1e6 * 1 10 |
+/ weaklings </ 1e6 * 1 10 |
||
37780 321750 |
37780 321750 |
||
</pre> |
|||
=={{header|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> |
|||
{{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> |
||