

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

   Safe primes and unsafe primes.


Also see

   The OEIS article A051634: strong primes.
   The OEIS article A051635: weak primes.


 
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;
                }
            }
        }
    }
 
}
 