Definitions

   A   safe prime   is a prime   p   and where   (p-1)/2   is also prime.
   The corresponding prime  (p-1)/2   is known as a   Sophie Germain   prime.
   An   unsafe prime   is a prime   p   and where   (p-1)/2   isn't   a prime.
   An   unsafe prime   is a prime that   isn't   a   safe   prime.


Task

   Find and display (on one line) the first   35   safe primes.
   Find and display the   count   of the safe primes below   1,000,000.
   Find and display the   count   of the safe primes below 10,000,000.
   Find and display (on one line) the first   40   unsafe primes.
   Find and display the   count   of the unsafe primes below   1,000,000.
   Find and display the   count   of the unsafe primes below 10,000,000.
   (Optional)   display the   counts   and   "below numbers"   with commas.
Show all output here.



Related Task

   strong and weak primes.


Also see

   The OEIS article:     safe   primes.
   The OEIS article:   unsafe primes.


 
BEGIN
 
    CLASS BOOLARRAY(N); INTEGER N;
    BEGIN
        BOOLEAN ARRAY DATA(0:N-1);
    END BOOLARRAY;
 
    CLASS INTARRAY(N); INTEGER N;
    BEGIN
        INTEGER ARRAY DATA(0:N-1);
    END INTARRAY;
 
    REF(BOOLARRAY) PROCEDURE SIEVE(LIMIT);
        INTEGER LIMIT;
    BEGIN
        REF(BOOLARRAY) C;
        INTEGER P, P2;
        LIMIT := LIMIT+1;
        COMMENT TRUE DENOTES COMPOSITE, FALSE DENOTES PRIME. ;
        C :- NEW BOOLARRAY(LIMIT); COMMENT ALL FALSE BY DEFAULT ;
        C.DATA(0) := TRUE;
        C.DATA(1) := TRUE;
        COMMENT APART FROM 2 ALL EVEN NUMBERS ARE OF COURSE COMPOSITE ;
        FOR I := 4 STEP 2 UNTIL LIMIT-1 DO
            C.DATA(I) := TRUE;
        COMMENT START FROM 3. ;
        P := 3;
        WHILE TRUE DO BEGIN
            P2 := P * P;
            IF P2 >= LIMIT THEN BEGIN
                GO TO OUTER_BREAK;
            END;
            I := P2;
            WHILE I < LIMIT DO BEGIN
                C.DATA(I) := TRUE;
                I := I + 2 * P;
            END;
            WHILE TRUE DO BEGIN
                P := P + 2;
                IF NOT C.DATA(P) THEN BEGIN
                    GO TO INNER_BREAK;
                END;
            END;
            INNER_BREAK:
        END;
        OUTER_BREAK:
        SIEVE :- C;
    END SIEVE;
 
    COMMENT MAIN BLOCK ;
 
    REF(BOOLARRAY) SIEVED;
    REF(INTARRAY) UNSAFE, SAFE;
    INTEGER I, COUNT;
 
    COMMENT SIEVE UP TO 10 MILLION ;
    SIEVED :- SIEVE(10000000);
 
    SAFE :- NEW INTARRAY(35);
    COUNT := 0;
    I := 3;
    WHILE COUNT < 35 DO BEGIN
        IF NOT SIEVED.DATA(I) AND NOT SIEVED.DATA((I-1)//2) THEN BEGIN
            SAFE.DATA(COUNT) := I;
            COUNT := COUNT+1;
        END;
        I := I+2;
    END;
    OUTTEXT("THE FIRST 35 SAFE PRIMES ARE:");
    OUTIMAGE;
    OUTCHAR('[');
    FOR I := 0 STEP 1 UNTIL 35-1 DO BEGIN
        IF I>0 THEN OUTCHAR(' ');
        OUTINT(SAFE.DATA(I), 0);
    END;
    OUTCHAR(']');
    OUTIMAGE;
    OUTIMAGE;
 
    COUNT := 0;
    FOR I := 3 STEP 2 UNTIL 1000000 DO BEGIN
        IF NOT SIEVED.DATA(I) AND NOT SIEVED.DATA((I-1)//2) THEN BEGIN
            COUNT := COUNT+1;
        END;
    END;
    OUTTEXT("THE NUMBER OF SAFE PRIMES BELOW 1,000,000 IS ");
    OUTINT(COUNT, 0);
    OUTIMAGE;
    OUTIMAGE;
 
    FOR I := 1000001 STEP 2 UNTIL 10000000 DO BEGIN
        IF NOT SIEVED.DATA(I) AND NOT SIEVED.DATA((I-1)//2) THEN
            COUNT := COUNT+1;
    END;
    OUTTEXT("THE NUMBER OF SAFE PRIMES BELOW 10,000,000 IS ");
    OUTINT(COUNT, 0);
    OUTIMAGE;
    OUTIMAGE;
 
    UNSAFE :- NEW INTARRAY(40);
    UNSAFE.DATA(0) := 2; COMMENT SINCE (2 - 1)/2 IS NOT PRIME ;
    COUNT := 1;
    I := 3;
    WHILE COUNT < 40 DO BEGIN
        IF NOT SIEVED.DATA(I) AND SIEVED.DATA((I-1)//2) THEN BEGIN
            UNSAFE.DATA(COUNT) := I;
            COUNT := COUNT+1;
        END;
        I := I+2;
    END;
    OUTTEXT("THE FIRST 40 UNSAFE PRIMES ARE:");
    OUTIMAGE;
    OUTCHAR('[');
    FOR I := 0 STEP 1 UNTIL 40-1 DO BEGIN
        IF I>0 THEN OUTCHAR(' ');
        OUTINT(UNSAFE.DATA(I), 0);
    END;
    OUTCHAR(']');
    OUTIMAGE;
    OUTIMAGE;
 
    COUNT := 1;
    FOR I := 3 STEP 2 UNTIL 1000000 DO BEGIN
        IF NOT SIEVED.DATA(I) AND SIEVED.DATA((I-1)//2) THEN
            COUNT := COUNT+1;
    END;
    OUTTEXT("THE NUMBER OF UNSAFE PRIMES BELOW 1,000,000 IS ");
    OUTINT(COUNT, 0);
    OUTIMAGE;
    OUTIMAGE;
 
    FOR I := 1000001 STEP 2 UNTIL 10000000 DO BEGIN
        IF NOT SIEVED.DATA(I) AND SIEVED.DATA((I-1)//2) THEN
            COUNT := COUNT+1;
    END;
    OUTTEXT("THE NUMBER OF UNSAFE PRIMES BELOW 10,000,000 IS ");
    OUTINT(COUNT, 0);
    OUTIMAGE;
 
 
END
 