Safe primes and unsafe primes

From Rosetta Code
Task
Safe primes and unsafe primes
You are encouraged to solve this task according to the task description, using any language you may know.
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


Also see



ALGOL 68[edit]

Works with: ALGOL 68G version Any - tested with release 2.8.3.win32
# find and count safe and unsafe primes                                       #
# safe primes are primes p such that ( p - 1 ) / 2 is also prime              #
# unsafe primes are primes that are not safe                                  #
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 prime                                    #
CHAR safe      = "S"; # safe prime                                            #
CHAR unsafe    = "U"; # unsafe 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 the maximum number                        #
[ 1 : max number ]CHAR primes;
sieve( primes );
# classify the primes                                                         #
# ( p - 1 ) OVER 2 is non-zero for p >= 3, thus we know 2 is unsafe           #
primes[ 2 ] := unsafe;
FOR p FROM 3 TO UPB primes DO
    IF primes[ p ] = prime THEN
        primes[ p ] := IF primes[ ( p - 1 ) OVER 2 ] = composite THEN unsafe ELSE safe FI
    FI
OD;
# count the primes of each type                                               #
INT safe1   := 0, safe10   := 0;
INT unsafe1 := 0, unsafe10 := 0;
FOR p FROM LWB primes TO UPB primes DO
    IF   primes[ p ] = safe  THEN
        safe10   +:= 1;
        IF p < 1 000 000 THEN safe1   +:= 1 FI
    ELIF primes[ p ] = unsafe THEN
        unsafe10 +:= 1;
        IF p < 1 000 000 THEN unsafe1 +:= 1 FI
    FI
OD;
INT safe count    := 0;
print( ( "first 35 safe   primes:", newline ) );
FOR p WHILE safe count   < 35 DO IF primes[ p ] = safe   THEN print( ( " ", whole( p, 0 ) ) ); safe count +:= 1 FI OD;
print( ( newline ) );
print( ( "safe   primes below   1,000,000: ", commatise(    safe1 ), newline ) );
print( ( "safe   primes below  10,000,000: ", commatise(   safe10 ), newline ) );
print( ( "first 40 unsafe primes:", newline ) );
INT unsafe count := 0;
FOR p WHILE unsafe count < 40 DO IF primes[ p ] = unsafe THEN print( ( " ", whole( p, 0 ) ) ); unsafe count +:= 1 FI OD;
print( ( newline ) );
print( ( "unsafe primes below   1,000,000: ", commatise(  unsafe1 ), newline ) );
print( ( "unsafe primes below  10,000,000: ", commatise( unsafe10 ), newline ) )
Output:
first 35 safe   primes:
 5 7 11 23 47 59 83 107 167 179 227 263 347 359 383 467 479 503 563 587 719 839 863 887 983 1019 1187 1283 1307 1319 1367 1439 1487 1523 1619
safe   primes below   1,000,000: 4,324
safe   primes below  10,000,000: 30,657
first 40 unsafe primes:
 2 3 13 17 19 29 31 37 41 43 53 61 67 71 73 79 89 97 101 103 109 113 127 131 137 139 149 151 157 163 173 181 191 193 197 199 211 223 229 233
unsafe primes below   1,000,000: 74,174
unsafe primes below  10,000,000: 633,922

AppleScript[edit]

-- Heavy-duty Sieve of Eratosthenes handler.
-- Returns a list containing either just the primes up to a given limit ('crossingsOut' = false) or, as in this task,
-- both the primes and 'missing values' representing the "crossed out" non-primes ('crossingsOut' = true).
on sieveForPrimes given limit:limit, crossingsOut:keepingZaps
    if (limit < 1) then return {}
    -- Build a list initially containing only 'missing values'. For speed, and to reduce the likelihood of hanging,
    -- do this by building sublists of at most 5000 items and concatenating them afterwards.
    script o
        property sublists : {}
        property numberList : {}
    end script
    set sublistSize to 5000
    set mv to missing value -- Use a single 'missing value' instance for economy.
    repeat sublistSize times
        set end of o's numberList to mv
    end repeat
    -- Start with a possible < 5000-item sublist.
    if (limit mod sublistSize > 0) then set end of o's sublists to items 1 thru (limit mod sublistSize) of o's numberList
    -- Then any 5000-item sublists needed.
    if (limit  sublistSize) then
        set end of o's sublists to o's numberList
        repeat (limit div sublistSize - 1) times
            set end of o's sublists to o's numberList's items
        end repeat
    end if
    -- Concatenate them more-or-less evenly.
    set subListCount to (count o's sublists)
    repeat until (subListCount is 1)
        set o's numberList to {}
        repeat with i from 2 to subListCount by 2
            set end of o's numberList to (item (i - 1) of o's sublists) & (item i of o's sublists)
        end repeat
        if (i < subListCount) then set last item of o's numberList to (end of o's numberList) & (end of o's sublists)
        set o's sublists to o's numberList
        set subListCount to subListCount div 2
    end repeat
    set o's numberList to beginning of o's sublists
    
    -- Set the relevant list positions to 2, 3, 5, and numbers which aren't multiples of them.
    if (limit > 1) then set item 2 of o's numberList to 2
    if (limit > 2) then set item 3 of o's numberList to 3
    if (limit > 4) then set item 5 of o's numberList to 5
    if (limit < 36) then
        set n to -23
    else
        repeat with n from 7 to (limit - 29) by 30
            set item n of o's numberList to n
            tell (n + 4) to set item it of o's numberList to it
            tell (n + 6) to set item it of o's numberList to it
            tell (n + 10) to set item it of o's numberList to it
            tell (n + 12) to set item it of o's numberList to it
            tell (n + 16) to set item it of o's numberList to it
            tell (n + 22) to set item it of o's numberList to it
            tell (n + 24) to set item it of o's numberList to it
        end repeat
    end if
    repeat with n from (n + 30) to limit
        if ((n mod 2 > 0) and (n mod 3 > 0) and (n mod 5 > 0)) then set item n of o's numberList to n
    end repeat
    
    -- "Cross out" inserted numbers which are multiples of others.
    set inx to {0, 4, 6, 10, 12, 16, 22, 24}
    repeat with n from 7 to ((limit ^ 0.5) div 1) by 30
        repeat with inc in inx
            tell (n + inc)
                if (item it of o's numberList is it) then
                    repeat with multiple from (it * it) to limit by it
                        set item multiple of o's numberList to mv
                    end repeat
                end if
            end tell
        end repeat
    end repeat
    
    if (keepingZaps) then return o's numberList
    return o's numberList's numbers
end sieveForPrimes

-- Task code:
on doTask()
    set {safeQuantity, unsafeQuantity, max1, max2} to {35, 40, 1000000 - 1, 10000000 - 1}
    set {safePrimes, unsafePrimes, safeCount1, safeCount2, unsafeCount1, unsafeCount2} to {{}, {}, 0, 0, 0, 0}
    -- Get a list of 9,999,999 primes and "crossed out" non-primes! Also one with just the primes.
    script o
        property primesAndZaps : sieveForPrimes with crossingsOut given limit:max2
        property primesOnly : my primesAndZaps's numbers
    end script
    -- Work through the primes-only list, using the other as an indexable look-up to check the related numbers.
    set SophieGermainLimit to (max2 - 1) div 2
    repeat with n in o's primesOnly
        set n to n's contents
        if (n  SophieGermainLimit) then
            tell (n * 2 + 1)
                if (item it of o's primesAndZaps is it) then
                    if (safeCount2 < safeQuantity) then set end of safePrimes to it
                    if (it < max1) then set safeCount1 to safeCount1 + 1
                    set safeCount2 to safeCount2 + 1
                end if
            end tell
        end if
        if ((n is 2) or (item ((n - 1) div 2) of o's primesAndZaps is missing value)) then
            if (unsafeCount2 < unsafeQuantity) then set end of unsafePrimes to n
            if (n < max1) then set unsafeCount1 to unsafeCount1 + 1
            set unsafeCount2 to unsafeCount2 + 1
        end if
    end repeat
    -- Format and output the results.
    set output to {}
    set astid to AppleScript's text item delimiters
    set AppleScript's text item delimiters to ", "
    set end of output to "First 35 safe primes:"
    set end of output to safePrimes as text
    set end of output to "There are " & safeCount1 & " safe primes < 1,000,000 and " & safeCount2 & " < 10,000,000."
    set end of output to ""
    set end of output to "First 40 unsafe primes:"
    set end of output to unsafePrimes as text
    set end of output to "There are " & unsafeCount1 & " unsafe primes < 1,000,000 and " & unsafeCount2 & " < 10,000,000."
    set AppleScript's text item delimiters to linefeed
    set output to output as text
    set AppleScript's text item delimiters to astid
    
    return output
end doTask

return doTask()
Output:
"First 35 safe primes:
5, 7, 11, 23, 47, 59, 83, 107, 167, 179, 227, 263, 347, 359, 383, 467, 479, 503, 563, 587, 719, 839, 863, 887, 983, 1019, 1187, 1283, 1307, 1319, 1367, 1439, 1487, 1523, 1619
There are 4324 safe primes < 1,000,000 and 30657 < 10,000,000.

First 40 unsafe primes:
2, 3, 13, 17, 19, 29, 31, 37, 41, 43, 53, 61, 67, 71, 73, 79, 89, 97, 101, 103, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 173, 181, 191, 193, 197, 199, 211, 223, 229, 233
There are 74174 unsafe primes < 1,000,000 and 633922 < 10,000,000."

AWK[edit]

# syntax: GAWK -f SAFE_PRIMES_AND_UNSAFE_PRIMES.AWK
BEGIN {
    for (i=1; i<1E7; i++) {
      if (is_prime(i)) {
        arr[i] = ""
      }
    }
# safe:
    stop1 = 35 ; stop2 = 1E6 ; stop3 = 1E7
    count1 = count2 = count3 = 0
    printf("The first %d safe primes:",stop1)
    for (i=3; count1<stop1; i+=2) {
      if (i in arr && ((i-1)/2 in arr)) {
        count1++
        printf(" %d",i)
      }
    }
    printf("\n")
    for (i=3; i<stop3; i+=2) {
      if (i in arr && ((i-1)/2 in arr)) {
        count3++
        if (i < stop2) {
          count2++
        }
      }
    }
    printf("Number below %d: %d\n",stop2,count2)
    printf("Number below %d: %d\n",stop3,count3)
# unsafe:
    stop1 = 40 ; stop2 = 1E6 ; stop3 = 1E7
    count1 = count2 = count3 = 1 # since (2-1)/2 is not prime
    printf("The first %d unsafe primes: 2",stop1)
    for (i=3; count1<stop1; i+=2) {
      if (i in arr && !((i-1)/2 in arr)) {
        count1++
        printf(" %d",i)
      }
    }
    printf("\n")
    for (i=3; i<stop3; i+=2) {
      if (i in arr && !((i-1)/2 in arr)) {
        count3++
        if (i < stop2) {
          count2++
        }
      }
    }
    printf("Number below %d: %d\n",stop2,count2)
    printf("Number below %d: %d\n",stop3,count3)
    exit(0)
}
function is_prime(n,  d) {
    d = 5
    if (n < 2) { return(0) }
    if (n % 2 == 0) { return(n == 2) }
    if (n % 3 == 0) { return(n == 3) }
    while (d*d <= n) {
      if (n % d == 0) { return(0) }
      d += 2
      if (n % d == 0) { return(0) }
      d += 4
    }
    return(1)
}
Output:
The first 35 safe primes: 5 7 11 23 47 59 83 107 167 179 227 263 347 359 383 467 479 503 563 587 719 839 863 887 983 1019 1187 1283 1307 1319 1367 1439 1487 1523 1619
Number below 1000000: 4324
Number below 10000000: 30657
The first 40 unsafe primes: 2 3 13 17 19 29 31 37 41 43 53 61 67 71 73 79 89 97 101 103 109 113 127 131 137 139 149 151 157 163 173 181 191 193 197 199 211 223 229 233
Number below 1000000: 74174
Number below 10000000: 633922


BASIC256[edit]

Translation of: FreeBASIC
arraybase 1
max = 1000000
sc1 = 0: usc1 = 0: sc2 = 0: usc2 = 0
safeprimes$ =""
unsafeprimes$ = ""

redim criba(max)
# False = prime, True = no prime
criba[0] = True
criba[1] = True

for i = 4 to max step 2
  criba[i] = 1
next i
for i = 3 to sqr(max) +1 step 2
  if criba[i] = False then
    for j = i * i to max step i * 2
      criba[j] = True
    next j
  end if
next

usc1 = 1
unsafeprimes$ = "2"
for i = 3 to 3001 step 2
  if criba[i] = False then
    if criba[i \ 2] = False then
      sc1 += 1
      if sc1 <= 35 then safeprimes$ += " " + string(i)
    else
      usc1 += 1
      if usc1 <= 40 then unsafeprimes$ +=  " " + string(i)
    end if
  end if
next i

for i = 3003 to max \ 10 step 2
  if criba[i] = False then
    if criba[i \ 2] = False then
      sc1 += 1
    else
      usc1 += 1
    end if
  end if
next i

sc2 = sc1
usc2 = usc1
for i = max \ 10 + 1 to max step 2
  if criba[i] = False then
    if criba[i \ 2] = False  then
      sc2 += 1
    else
      usc2 += 1
    end if
  end if
next i

print "the first 35 Safeprimes are: "; safeprimes$
print
print "the first 40 Unsafeprimes are:  "; unsafeprimes$
print
print "     Safeprimes   Unsafeprimes"
print "  Below  -------------------------"
print max \ 10, sc1, usc1
print max   , sc2, usc2
end


C[edit]

#include <stdbool.h>
#include <stdio.h>

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
};
#define PCOUNT (sizeof(primes) / sizeof(int))

bool isPrime(int n) {
    int i;

    if (n < 2) {
        return false;
    }

    for (i = 0; i < PCOUNT; i++) {
        if (n == primes[i]) {
            return true;
        }
        if (n % primes[i] == 0) {
            return false;
        }
        if (n < primes[i] * primes[i]) {
            return true;
        }
    }

    for (i = primes[PCOUNT - 1] + 2; i * i <= n; i += 2) {
        if (n % i == 0) {
            return false;
        }
    }

    return true;
}

int main() {
    int beg, end;
    int i, count;

    // safe primes
    ///////////////////////////////////////////
    beg = 2;
    end = 1000000;
    count = 0;
    printf("First 35 safe primes:\n");
    for (i = beg; i < end; i++) {
        if (isPrime(i) && isPrime((i - 1) / 2)) {
            if (count < 35) {
                printf("%d ", i);
            }
            count++;
        }
    }
    printf("\nThere are  %d safe primes below  %d\n", count, end);

    beg = end;
    end = end * 10;
    for (i = beg; i < end; i++) {
        if (isPrime(i) && isPrime((i - 1) / 2)) {
            count++;
        }
    }
    printf("There are %d safe primes below %d\n", count, end);

    // unsafe primes
    ///////////////////////////////////////////
    beg = 2;
    end = 1000000;
    count = 0;
    printf("\nFirst 40 unsafe primes:\n");
    for (i = beg; i < end; i++) {
        if (isPrime(i) && !isPrime((i - 1) / 2)) {
            if (count < 40) {
                printf("%d ", i);
            }
            count++;
        }
    }
    printf("\nThere are  %d unsafe primes below  %d\n", count, end);

    beg = end;
    end = end * 10;
    for (i = beg; i < end; i++) {
        if (isPrime(i) && !isPrime((i - 1) / 2)) {
            count++;
        }
    }
    printf("There are %d unsafe primes below %d\n", count, end);

    return 0;
}
Output:
First 35 safe primes:
5 7 11 23 47 59 83 107 167 179 227 263 347 359 383 467 479 503 563 587 719 839 863 887 983 1019 1187 1283 1307 1319 1367 1439 1487 1523 1619
There are  4324 safe primes below  1000000
There are 30657 safe primes below 10000000

First 40 unsafe primes:
2 3 13 17 19 29 31 37 41 43 53 61 67 71 73 79 89 97 101 103 109 113 127 131 137 139 149 151 157 163 173 181 191 193 197 199 211 223 229 233
There are  74174 unsafe primes below  1000000
There are 633922 unsafe primes below 10000000

C#[edit]

Works with: C sharp version 7
using static System.Console;
using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;

public static class SafePrimes
{
    public static void Main() {
        HashSet<int> primes = Primes(10_000_000).ToHashSet();
        WriteLine("First 35 safe primes:");
        WriteLine(string.Join(" ", primes.Where(IsSafe).Take(35)));
        WriteLine($"There are {primes.TakeWhile(p => p < 1_000_000).Count(IsSafe):n0} safe primes below {1_000_000:n0}");
        WriteLine($"There are {primes.TakeWhile(p => p < 10_000_000).Count(IsSafe):n0} safe primes below {10_000_000:n0}");
        WriteLine("First 40 unsafe primes:");
        WriteLine(string.Join(" ", primes.Where(IsUnsafe).Take(40)));
        WriteLine($"There are {primes.TakeWhile(p => p < 1_000_000).Count(IsUnsafe):n0} unsafe primes below {1_000_000:n0}");
        WriteLine($"There are {primes.TakeWhile(p => p < 10_000_000).Count(IsUnsafe):n0} unsafe primes below {10_000_000:n0}");

        bool IsSafe(int prime) => primes.Contains(prime / 2);
        bool IsUnsafe(int prime) => !primes.Contains(prime / 2);
    }

    //Method from maths library
    static IEnumerable<int> Primes(int bound) {
        if (bound < 2) yield break;
        yield return 2;

        BitArray composite = new BitArray((bound - 1) / 2);
        int limit = ((int)(Math.Sqrt(bound)) - 1) / 2;
        for (int i = 0; i < limit; i++) {
            if (composite[i]) continue;
            int prime = 2 * i + 3;
            yield return prime;
            for (int j = (prime * prime - 2) / 2; j < composite.Count; j += prime) composite[j] = true;
        }
        for (int i = limit; i < composite.Count; i++) {
            if (!composite[i]) yield return 2 * i + 3;
        }
    }

}
Output:
First 35 safe primes:
5 7 11 23 47 59 83 107 167 179 227 263 347 359 383 467 479 503 563 587 719 839 863 887 983 1019 1187 1283 1307 1319 1367 1439 1487 1523 1619
There are 4,324 safe primes below 1,000,000
There are 30,657 safe primes below 10,000,000
First 40 unsafe primes:
2 3 13 17 19 29 31 37 41 43 53 61 67 71 73 79 89 97 101 103 109 113 127 131 137 139 149 151 157 163 173 181 191 193 197 199 211 223 229 233
There are 74,174 unsafe primes below 1,000,000
There are 633,922 unsafe primes below 10,000,000

C++[edit]

#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() {
    // find the prime numbers up to limit2
    prime_sieve sieve(limit2);

    // write numbers with groups of digits separated according to the system default locale
    std::cout.imbue(std::locale(""));

    // count and print safe/unsafe prime numbers
    prime_info safe_primes(35);
    prime_info unsafe_primes(40);
    for (int p = 2; p < limit2; ++p) {
        if (sieve.is_prime(p)) {
            if (sieve.is_prime((p - 1)/2))
                safe_primes.add_prime(p);
            else
                unsafe_primes.add_prime(p);
        }
    }
    safe_primes.print(std::cout, "safe");
    unsafe_primes.print(std::cout, "unsafe");
    return 0;
}

Contents of prime_sieve.hpp:

#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
Output:
First 35 safe primes: 5 7 11 23 47 59 83 107 167 179 227 263 347 359 383 467 479 503 563 587 719 839 863 887 983 1,019 1,187 1,283 1,307 1,319 1,367 1,439 1,487 1,523 1,619 
Number of safe primes below 1,000,000: 4,324
Number of safe primes below 10,000,000: 30,657
First 40 unsafe primes: 2 3 13 17 19 29 31 37 41 43 53 61 67 71 73 79 89 97 101 103 109 113 127 131 137 139 149 151 157 163 173 181 191 193 197 199 211 223 229 233 
Number of unsafe primes below 1,000,000: 74,174
Number of unsafe primes below 10,000,000: 633,922

CLU[edit]

isqrt = proc (s: int) returns (int)
    x0: int := s/2
    if x0=0 then return(s) end
    x1: int := (x0 + s/x0)/2
    while x1 < x0 do
        x0 := x1
        x1 := (x0 + s/x0)/2
    end
    return(x0)
end isqrt

sieve = proc (n: int) returns (array[bool])
    prime: array[bool] := array[bool]$fill(0,n+1,true)
    prime[0] := false
    prime[1] := false
    for p: int in int$from_to(2, isqrt(n)) do
        if prime[p] then
            for c: int in int$from_to_by(p*p,n,p) do
                prime[c] := false
            end
        end
    end
    return(prime)
end sieve

start_up = proc ()
    primeinfo = record [
        name: string,
        ps: array[int],
        maxps, n_1e6, n_1e7: int
    ]
    
    po: stream := stream$primary_output()
    prime: array[bool] := sieve(10000000)
    
    safe: primeinfo := primeinfo${
        name: "safe",
        ps: array[int]$[],
        maxps: 35,
        n_1e6: 0,
        n_1e7: 0
    }
    
    unsafe: primeinfo := primeinfo${
        name: "unsafe",
        ps: array[int]$[],
        maxps: 40,
        n_1e6: 0,
        n_1e7: 0
    }
 
    for p: int in int$from_to(2, 10000000) do
        if ~prime[p] then continue end
        ir: primeinfo 
        if prime[(p-1)/2] 
            then ir := safe 
            else ir := unsafe
        end
        
        if array[int]$size(ir.ps) < ir.maxps then
            array[int]$addh(ir.ps,p)
        end
        if p<1000000 then ir.n_1e6 := ir.n_1e6 + 1 end
        if p<10000000 then ir.n_1e7 := ir.n_1e7 + 1 end
    end
    
    for ir: primeinfo in array[primeinfo]$elements(
                       array[primeinfo]$[safe, unsafe]) do
        stream$putl(po, "First " || int$unparse(ir.maxps)
                   || " " || ir.name || " primes:")
        for i: int in array[int]$elements(ir.ps) do
            stream$puts(po, int$unparse(i) || " ")
        end
        stream$putl(po, "\nThere are " || int$unparse(ir.n_1e6)
                      || " " || ir.name || " primes < 1,000,000.")
        stream$putl(po, "There are " || int$unparse(ir.n_1e7)
                      || " " || ir.name || " primes < 1,000,000.\n")
    end
end start_up
Output:
First 35 safe primes:
5 7 11 23 47 59 83 107 167 179 227 263 347 359 383 467 479 503 563 587 719 839 863 887 983 1019 1187 1283 1307 1319 1367 1439 1487 1523 1619
There are 4324 safe primes < 1,000,000.
There are 30657 safe primes < 1,000,000.

First 40 unsafe primes:
2 3 13 17 19 29 31 37 41 43 53 61 67 71 73 79 89 97 101 103 109 113 127 131 137 139 149 151 157 163 173 181 191 193 197 199 211 223 229 233
There are 74174 unsafe primes < 1,000,000.
There are 633922 unsafe primes < 1,000,000.

D[edit]

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

bool isPrime(const int n) {
    if (n < 2) {
        return false;
    }

    foreach (p; PRIMES) {
        if (n == p) {
            return true;
        }
        if (n % p == 0) {
            return false;
        }
        if (n < p * p) {
            return true;
        }
    }

    int i = (PRIMES[$ - 1] / 6) * 6 - 1;
    while (i * i <= n) {
        if (n % i == 0) {
            return false;
        }
        i += 2;
        if (n % i == 0) {
            return false;
        }
        i += 4;
    }

    return true;
}

void main() {
    int beg = 2;
    int end = 1_000_000;
    int count = 0;

    // safe primes
    ///////////////////////////////////////////

    writeln("First 35 safe primes:");
    foreach (i; beg..end) {
        if (isPrime(i) && isPrime((i - 1) / 2)) {
            if (count < 35) {
                write(i, ' ');
            }
            count++;
        }
    }
    writefln("\nThere are %5d safe primes below %8d", count, end);

    beg = end;
    end *= 10;
    foreach (i; beg..end) {
        if (isPrime(i) && isPrime((i - 1) / 2)) {
            count++;
        }
    }
    writefln("There are %5d safe primes below %8d", count, end);

    // unsafe primes
    ///////////////////////////////////////////

    beg = 2;
    end = 1_000_000;
    count = 0;
    writeln("\nFirst 40 unsafe primes:");
    foreach (i; beg..end) {
        if (isPrime(i) && !isPrime((i - 1) / 2)) {
            if (count < 40) {
                write(i, ' ');
            }
            count++;
        }
    }
    writefln("\nThere are %6d unsafe primes below %9d", count, end);

    beg = end;
    end *= 10;
    foreach (i; beg..end) {
        if (isPrime(i) && !isPrime((i - 1) / 2)) {
            count++;
        }
    }
    writefln("There are %6d unsafe primes below %9d", count, end);
}
Output:
First 35 safe primes:
5 7 11 23 47 59 83 107 167 179 227 263 347 359 383 467 479 503 563 587 719 839 863 887 983 1019 1187 1283 1307 1319 1367 1439 1487 1523 1619
There are  4324 safe primes below  1000000
There are 30657 safe primes below 10000000

First 40 unsafe primes:
2 3 13 17 19 29 31 37 41 43 53 61 67 71 73 79 89 97 101 103 109 113 127 131 137 139 149 151 157 163 173 181 191 193 197 199 211 223 229 233
There are  74174 unsafe primes below   1000000
There are 633922 unsafe primes below  10000000

F#[edit]

This task uses Extensible Prime Generator (F#)
pCache |> Seq.filter(fun n->isPrime((n-1)/2)) |> Seq.take 35 |> Seq.iter (printf "%d ")
Output:
5 7 11 23 47 59 83 107 167 179 227 263 347 359 383 467 479 503 563 587 719 839 863 887 983 1019 1187 1283 1307 1319 1367 1439 1487 1523 1619
printfn "There are %d safe primes less than 1000000" (pCache |> Seq.takeWhile(fun n->n<1000000) |> Seq.filter(fun n->isPrime((n-1)/2)) |> Seq.length)
Output:
There are 4324 safe primes less than 10000000
printfn "There are %d safe primes less than 10000000" (pCache |> Seq.takeWhile(fun n->n<10000000) |> Seq.filter(fun n->isPrime((n-1)/2)) |> Seq.length)
Output:
There are 30657 safe primes less than 10000000
pCache |> Seq.filter(fun n->not (isPrime((n-1)/2))) |> Seq.take 40 |> Seq.iter (printf "%d ")
Output:
2 3 13 17 19 29 31 37 41 43 53 61 67 71 73 79 89 97 101 103 109 113 127 131 137 139 149 151 157 163 173 181 191 193 197 199 211 223 229 233
printfn "There are %d unsafe primes less than 1000000" (pCache |> Seq.takeWhile(fun n->n<1000000) |> Seq.filter(fun n->not (isPrime((n-1)/2))) |> Seq.length);;
Output:
There are 74174 unsafe primes less than 1000000
printfn "There are %d unsafe primes less than 10000000" (pCache |> Seq.takeWhile(fun n->n<10000000) |> Seq.filter(fun n->not (isPrime((n-1)/2))) |> Seq.length);;
Output:
There are 633922 unsafe primes less than 10000000

Factor[edit]

Much like the Raku example, this program uses an in-built primes generator to efficiently obtain the first ten million primes. If memory is a concern, it wouldn't be unreasonable to perform primality tests on the (odd) numbers below ten million, however.

USING: fry interpolate kernel literals math math.primes
sequences tools.memory.private ;
IN: rosetta-code.safe-primes

CONSTANT: primes $[ 10,000,000 primes-upto ]

: safe/unsafe ( -- safe unsafe )
    primes [ 1 - 2/ prime? ] partition ;

: count< ( seq n -- str ) '[ _ < ] count commas ;

: seq>commas ( seq -- str ) [ commas ] map " " join ;

: stats ( seq n -- head count1 count2 )
    '[ _ head seq>commas ] [ 1e6 count< ] [ 1e7 count< ] tri ;

safe/unsafe [ 35 ] [ 40 ] bi* [ stats ] 2bi@

[I
First 35 safe primes:
${5}
Safe prime count below  1,000,000: ${4}
Safe prime count below 10,000,000: ${3}

First 40 unsafe primes:
${2}
Unsafe prime count below  1,000,000: ${1}
Unsafe prime count below 10,000,000: ${}
I]
Output:
First 35 safe primes:
5 7 11 23 47 59 83 107 167 179 227 263 347 359 383 467 479 503 563 587 719 839 863 887 983 1,019 1,187 1,283 1,307 1,319 1,367 1,439 1,487 1,523 1,619
Safe prime count below  1,000,000: 4,324
Safe prime count below 10,000,000: 30,657

First 40 unsafe primes:
2 3 13 17 19 29 31 37 41 43 53 61 67 71 73 79 89 97 101 103 109 113 127 131 137 139 149 151 157 163 173 181 191 193 197 199 211 223 229 233
Unsafe prime count below  1,000,000: 74,174
Unsafe prime count below 10,000,000: 633,922

FreeBASIC[edit]

' version 19-01-2019
' compile with: fbc -s console

Const As UInteger max = 10000000
Dim As UInteger i, j, sc1, usc1, sc2, usc2
Dim As String safeprimes, unsafeprimes
Dim As UByte sieve()

ReDim sieve(max)
' 0 = prime, 1 = no prime
sieve(0) = 1 : sieve(1) = 1

For i = 4 To max Step 2
    sieve(i) = 1
Next
For i = 3 To Sqr(max) +1 Step 2
    If sieve(i) = 0 Then
        For j = i * i To max Step i * 2
            sieve(j) = 1
        Next
    End If
Next

usc1 = 1 : unsafeprimes = "2"
For i = 3 To 3001 Step 2
    If sieve(i) = 0 Then
        If sieve(i \ 2) = 0 Then
            sc1 += 1
            If sc1 <= 35 Then
                safeprimes += " " + Str(i)
            End If
        Else
            usc1 += 1
            If usc1 <= 40 Then
                unsafeprimes +=  " " + Str(i)
            End If
        End If
    End If
Next

For i = 3003 To max \ 10 Step 2
    If sieve(i) = 0 Then
        If sieve(i \ 2) = 0 Then
            sc1 += 1
        Else
            usc1 += 1
        End If
    End If
Next

sc2 = sc1 : usc2 = usc1
For i = max \ 10 +1 To max Step 2
    If sieve(i) = 0 Then
        If sieve(i \ 2) = 0  Then
            sc2 += 1
        Else
            usc2 += 1
        End If
    End If
Next

Print "the first 35 Safeprimes are: "; safeprimes
Print
Print "the first 40 Unsafeprimes are:  "; unsafeprimes
Print
Print "                  Safeprimes     Unsafeprimes"
Print "    Below         ---------------------------"
Print Using "##########,      ";  max \ 10; sc1; usc1
Print Using "##########,      ";  max     ; sc2; usc2

' empty keyboard buffer
While Inkey <> "" : Wend
Print : Print "hit any key to end program"
Sleep
End
Output:
the first 35 Safeprimes are:  5 7 11 23 47 59 83 107 167 179 227 263 347 359 383 467 479 503 563 587 719 839 863 887 983 1019 1187 1283 1307 1319 1367 1439 1487 1523 1619

the first 40 Unsafeprimes are:  2 3 13 17 19 29 31 37 41 43 53 61 67 71 73 79 89 97 101 103 109 113 127 131 137 139 149 151 157 163 173 181 191 193 197 199 211 223 229 233

                  Safeprimes     Unsafeprimes
    Below         ---------------------------
  1,000,000            4,324           74,174
 10,000,000           30,657          633,922

Frink[edit]

safePrimes[end=undef] := select[primes[5,end], {|p| isPrime[(p-1)/2] }]
unsafePrimes[end=undef] := select[primes[2,end], {|p| p<5 or isPrime[(p-1)/2] }]

println["First 35 safe primes:  " + first[safePrimes[], 35]]
println["Safe primes below  1,000,000: " + length[safePrimes[1_000_000]]]
println["Safe primes below 10,000,000: " + length[safePrimes[10_000_000]]]

println["First 40 unsafe primes:  " + first[unsafePrimes[], 40]]
println["Unsafe primes below  1,000,000: " + length[unsafePrimes[1_000_000]]]
println["Unsafe primes below 10,000,000: " + length[unsafePrimes[10_000_000]]]
Output:
First 35 safe primes:  [5, 7, 11, 23, 47, 59, 83, 107, 167, 179, 227, 263, 347, 359, 383, 467, 479, 503, 563, 587, 719, 839, 863, 887, 983, 1019, 1187, 1283, 1307, 1319, 1367, 1439, 1487, 1523, 1619]
Safe primes below  1,000,000: 4324
Safe primes below 10,000,000: 30657
First 40 unsafe primes:  [2, 3, 13, 17, 19, 29, 31, 37, 41, 43, 53, 61, 67, 71, 73, 79, 89, 97, 101, 103, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 173, 181, 191, 193, 197, 199, 211, 223, 229, 233]
Unsafe primes below  1,000,000: 74174
Unsafe primes below 10,000,000: 633922

Go[edit]

package main

import "fmt"

func sieve(limit uint64) []bool {
    limit++
    // True denotes composite, false denotes prime.
    c := make([]bool, limit) // all false by default
    c[0] = true
    c[1] = true
    // apart from 2 all even numbers are of course composite
    for i := uint64(4); i < limit; i += 2 {
        c[i] = true
    }
    p := uint64(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)
    if n < 0 {
        s = s[1:]
    }
    le := len(s)
    for i := le - 3; i >= 1; i -= 3 {
        s = s[0:i] + "," + s[i:]
    }
    if n >= 0 {
        return s
    }
    return "-" + s
}

func main() {
    // sieve up to 10 million
    sieved := sieve(1e7)
    var safe = make([]int, 35)
    count := 0
    for i := 3; count < 35; i += 2 {
        if !sieved[i] && !sieved[(i-1)/2] {
            safe[count] = i
            count++
        }
    }
    fmt.Println("The first 35 safe primes are:\n", safe, "\n")

    count = 0
    for i := 3; i < 1e6; i += 2 {
        if !sieved[i] && !sieved[(i-1)/2] {
            count++
        }
    }
    fmt.Println("The number of safe primes below 1,000,000 is", commatize(count), "\n")

    for i := 1000001; i < 1e7; i += 2 {
        if !sieved[i] && !sieved[(i-1)/2] {
            count++
        }
    }
    fmt.Println("The number of safe primes below 10,000,000 is", commatize(count), "\n")

    unsafe := make([]int, 40)
    unsafe[0] = 2 // since (2 - 1)/2 is not prime
    count = 1
    for i := 3; count < 40; i += 2 {
        if !sieved[i] && sieved[(i-1)/2] {
            unsafe[count] = i
            count++
        }
    }
    fmt.Println("The first 40 unsafe primes are:\n", unsafe, "\n")

    count = 1
    for i := 3; i < 1e6; i += 2 {
        if !sieved[i] && sieved[(i-1)/2] {
            count++
        }
    }
    fmt.Println("The number of unsafe primes below 1,000,000 is", commatize(count), "\n")

    for i := 1000001; i < 1e7; i += 2 {
        if !sieved[i] && sieved[(i-1)/2] {
            count++
        }
    }
    fmt.Println("The number of unsafe primes below 10,000,000 is", commatize(count), "\n")
}
Output:
The first 35 safe primes are:
 [5 7 11 23 47 59 83 107 167 179 227 263 347 359 383 467 479 503 563 587 719 839 863 887 983 1019 1187 1283 1307 1319 1367 1439 1487 1523 1619] 

The number of safe primes below 1,000,000 is 4,324 

The number of safe primes below 10,000,000 is 30,657 

The first 40 unsafe primes are:
 [2 3 13 17 19 29 31 37 41 43 53 61 67 71 73 79 89 97 101 103 109 113 127 131 137 139 149 151 157 163 173 181 191 193 197 199 211 223 229 233] 

The number of unsafe primes below 1,000,000 is 74,174 

The number of unsafe primes below 10,000,000 is 633,922 

Haskell[edit]

Uses Numbers.Prime library: http://hackage.haskell.org/package/primes-0.2.1.0/docs/Data-Numbers-Primes.html

import Text.Printf (printf)
import Data.Numbers.Primes (isPrime, primes)

main = do 
  printf "First 35 safe primes: %s\n" (show $ take 35 safe)
  printf "There are %d safe primes below 100,000.\n" (length $ takeWhile (<1000000) safe)
  printf "There are %d safe primes below 10,000,000.\n\n" (length $ takeWhile (<10000000) safe)

  printf "First 40 unsafe primes: %s\n" (show $ take 40 unsafe)
  printf "There are %d unsafe primes below 100,000.\n" (length $ takeWhile (<1000000) unsafe)
  printf "There are %d unsafe primes below 10,000,000.\n\n" (length $ takeWhile (<10000000) unsafe)

  where safe = filter (\n -> isPrime ((n-1) `div` 2)) primes
        unsafe = filter (\n -> not (isPrime((n-1) `div` 2))) primes
Output:
First 35 safe primes: [5,7,11,23,47,59,83,107,167,179,227,263,347,359,383,467,479,503,563,587,719,839,863,887,983,1019,1187,1283,1307,1319,1367,1439,1487,1523,1619]
There are 4324 safe primes below 100,000.
There are 30657 safe primes below 10,000,000.

First 40 unsafe primes: [2,3,13,17,19,29,31,37,41,43,53,61,67,71,73,79,89,97,101,103,109,113,127,131,137,139,149,151,157,163,173,181,191,193,197,199,211,223,229,233]
There are 74174 unsafe primes below 100,000.
There are 633922 unsafe primes below 10,000,000.

J[edit]

   NB. play around a bit to get primes less than ten million
   p:inv 10000000
664579

   p:664579
10000019

   PRIMES =: p:i.664579
   10 {. PRIMES
2 3 5 7 11 13 17 19 23 29

   {: PRIMES
9999991


   primeQ =: 1&p:
   safeQ =: primeQ@:-:@:<:
   Filter =: (#~`)(`:6)

   SAFE =: safeQ Filter PRIMES

   NB. first thirty-five safe primes
   (32+3) {. SAFE
5 7 11 23 47 59 83 107 167 179 227 263 347 359 383 467 479 503 563 587 719 839 863 887 983 1019 1187 1283 1307 1319 1367 1439 1487 1523 1619
   

   NB. first forty unsafe primes
   (33+7) {. PRIMES -. SAFE
   2 3 13 17 19 29 31 37 41 43 53 61 67 71 73 79 89 97 101 103 109 113 127 131 137 139 149 151 157 163 173 181 191 193 197 199 211 223 229 233
   

   NB. tally of safe primes less than ten million
   # SAFE
30657
   

   NB. tally of safe primes below a million
   # 1000000&>Filter SAFE
4324
   

   NB. tally of perilous primes below ten million
   UNSAFE =: PRIMES -. SAFE

   # UNSAFE
633922
   

   NB. tally of these below one million
   K =: 1 : 'm * 1000'
   +/ UNSAFE < 1 K K
74174
   

Essentially we have

primeQ =: 1&p:
safeQ =: primeQ@:-:@:<: 
Filter =: (#~`)(`:6)
K =: adverb def 'm * 1000'
PRIMES =: i.&.:(p:inv) 10 K K
SAFE =: safeQ Filter PRIMES
UNSAFE =: PRIMES -. SAFE

The rest of the display is mere window dressing.

Java[edit]

public class SafePrimes {
    public static void main(String... args) {
        // Use Sieve of Eratosthenes to find primes
        int SIEVE_SIZE = 10_000_000;
        boolean[] isComposite = new boolean[SIEVE_SIZE];
        // It's really a flag indicating non-prime, but composite usually applies
        isComposite[0] = true;
        isComposite[1] = true;
        for (int n = 2; n < SIEVE_SIZE; n++) {
            if (isComposite[n]) {
                continue;
            }
            for (int i = n * 2; i < SIEVE_SIZE; i += n) {
                isComposite[i] = true;
            }
        }
        
        int oldSafePrimeCount = 0;
        int oldUnsafePrimeCount = 0;
        int safePrimeCount = 0;
        int unsafePrimeCount = 0;
        StringBuilder safePrimes = new StringBuilder();
        StringBuilder unsafePrimes = new StringBuilder();
        int safePrimesStrCount = 0;
        int unsafePrimesStrCount = 0;
        for (int n = 2; n < SIEVE_SIZE; n++) {
            if (n == 1_000_000) {
                oldSafePrimeCount = safePrimeCount;
                oldUnsafePrimeCount = unsafePrimeCount;
            }
            if (isComposite[n]) {
                continue;
            }
            boolean isUnsafe = isComposite[(n - 1) >>> 1];
            if (isUnsafe) {
                if (unsafePrimeCount < 40) {
                    if (unsafePrimeCount > 0) {
                        unsafePrimes.append(", ");
                    }
                    unsafePrimes.append(n);
                    unsafePrimesStrCount++;
                }
                unsafePrimeCount++;
            }
            else {
                if (safePrimeCount < 35) {
                    if (safePrimeCount > 0) {
                        safePrimes.append(", ");
                    }
                    safePrimes.append(n);
                    safePrimesStrCount++;
                }
                safePrimeCount++;
            }
        }
        
        System.out.println("First " + safePrimesStrCount + " safe primes: " + safePrimes.toString());
        System.out.println("Number of safe primes below 1,000,000: " + oldSafePrimeCount);
        System.out.println("Number of safe primes below 10,000,000: " + safePrimeCount);
        System.out.println("First " + unsafePrimesStrCount + " unsafe primes: " + unsafePrimes.toString());
        System.out.println("Number of unsafe primes below 1,000,000: " + oldUnsafePrimeCount);
        System.out.println("Number of unsafe primes below 10,000,000: " + unsafePrimeCount);
        
        return;
    }
}
Output:
First 35 safe primes: 5, 7, 11, 23, 47, 59, 83, 107, 167, 179, 227, 263, 347, 359, 383, 467, 479, 503, 563, 587, 719, 839, 863, 887, 983, 1019, 1187, 1283, 1307, 1319, 1367, 1439, 1487, 1523, 1619
Number of safe primes below 1,000,000: 4324
Number of safe primes below 10,000,000: 30657
First 40 unsafe primes: 2, 3, 13, 17, 19, 29, 31, 37, 41, 43, 53, 61, 67, 71, 73, 79, 89, 97, 101, 103, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 173, 181, 191, 193, 197, 199, 211, 223, 229, 233
Number of unsafe primes below 1,000,000: 74174
Number of unsafe primes below 10,000,000: 633922

jq[edit]

Works with: jq

To save memory, we use a memory-less `is_prime` algorithm, but with a long preamble.

def is_prime:
  . as $n
  | if ($n < 2)         then false
    elif ($n % 2 == 0)  then $n == 2
    elif ($n % 3 == 0)  then $n == 3
    elif ($n % 5 == 0)  then $n == 5
    elif ($n % 7 == 0)  then $n == 7
    elif ($n % 11 == 0) then $n == 11
    elif ($n % 13 == 0) then $n == 13
    elif ($n % 17 == 0) then $n == 17
    elif ($n % 19 == 0) then $n == 19
    elif ($n % 23 == 0) then $n == 23
    elif ($n % 29 == 0) then $n == 29
    elif ($n % 31 == 0) then $n == 31
    else 37
         | until( (. * .) > $n or ($n % . == 0); . + 2)
         | . * . > $n
    end;

def task:

  # a helper function for keeping count:
  def record($p; counter6; counter7):
    if $p < 10000000
    then counter7 += 1
    | if $p < 1000000 
      then counter6 += 1
      else .
      end
    else .
    end;

  # a helper function for recording up to $max values
  def recordValues($max; $p; a; done):
     if done then .
     elif a|length < $max
     then a += [$p] | done = ($max == (a|length))
     else .
     end;

  10000000 as $n
  | reduce (2, range(3;$n;2)) as $p ({};
      if $p|is_prime
      then if (($p - 1) / 2) | is_prime
           then recordValues(35; $p; .safeprimes; .safedone)
           | record($p; .nsafeprimes6; .nsafeprimes7)
           else  recordValues(40; $p; .unsafeprimes; .unsafedone)
           | record($p; .nunsafeprimes6; .nunsafeprimes7)
           end
      else .
      end )
  | "The first 35 safe primes are: ", .safeprimes[0:35],
    "\nThere are \(.nsafeprimes6) safe primes less than 1 million.",
    "\nThere are \(.nsafeprimes7) safe primes less than 10 million.",
    "",
    "\nThe first 40 unsafe primes are:", .unsafeprimes[0:40],
    "\nThere are \(.nunsafeprimes6) unsafe primes less than 1 million.",
    "\nThere are \(.nunsafeprimes7) unsafe primes less than 10 million."
;

task
Output:
The first 35 safe primes are: 
[5,7,11,23,47,59,83,107,167,179,227,263,347,359,383,467,479,503,563,587,719,839,863,887,983,1019,1187,1283,1307,1319,1367,1439,1487,1523,1619]

There are 4324 safe primes less than 1 million.

There are 30657 safe primes less than 10 million.


The first 40 unsafe primes are:
[2,3,13,17,19,29,31,37,41,43,53,61,67,71,73,79,89,97,101,103,109,113,127,131,137,139,149,151,157,163,173,181,191,193,197,199,211,223,229,233]

There are 74174 unsafe primes less than 1 million.

There are 633922 unsafe primes less than 10 million.

Julia[edit]

using Primes, Formatting

function parseprimelist()
    primelist = primes(2, 10000000)
    safeprimes = Vector{Int64}()
    unsafeprimes = Vector{Int64}()
    for p in primelist
        if isprime(div(p - 1, 2))
            push!(safeprimes, p)
        else
            push!(unsafeprimes, p)
        end
    end
    println("The first 35 unsafe primes are: ", safeprimes[1:35])
    println("There are ", format(sum(map(x -> x < 1000000, safeprimes)), commas=true), " safe primes less than 1 million.")
    println("There are ", format(length(safeprimes), commas=true), " safe primes less than 10 million.")    
    println("The first 40 unsafe primes are: ", unsafeprimes[1:40])
    println("There are ", format(sum(map(x -> x < 1000000, unsafeprimes)), commas=true), " unsafe primes less than 1 million.")
    println("There are ", format(length(unsafeprimes), commas=true), " unsafe primes less than 10 million.")
end

parseprimelist()
Output:

The first 35 unsafe primes are: [5, 7, 11, 23, 47, 59, 83, 107, 167, 179, 227, 263, 347, 359, 383, 467, 479, 503, 563, 587, 719, 839, 863, 887, 983, 1019, 1187, 1283, 1307, 1319, 1367, 1439, 1487, 1523, 1619] There are 4,324 safe primes less than 1 million. There are 30,657 safe primes less than 10 million. The first 40 unsafe primes are: [2, 3, 13, 17, 19, 29, 31, 37, 41, 43, 53, 61, 67, 71, 73, 79, 89, 97, 101, 103, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 173, 181, 191, 193, 197, 199, 211, 223, 229, 233] There are 74,174 unsafe primes less than 1 million. There are 633,922 unsafe primes less than 10 million.

Kotlin[edit]

Translation of: Go
// Version 1.2.70

fun sieve(limit: Int): BooleanArray {
    // True denotes composite, false denotes prime.
    val c = BooleanArray(limit + 1) // all false by default
    c[0] = true
    c[1] = true
    // apart from 2 all even numbers are of course composite
    for (i in 4..limit step 2) c[i] = true
    var p = 3 // start from 3
    while (true) {
        val p2 = p * p
        if (p2 > limit) break
        for (i in p2..limit step 2 * p) c[i] = true
        while (true) {
            p += 2
            if (!c[p]) break
        }
    }
    return c
}

fun main(args: Array<String>) {
    // sieve up to 10 million
    val sieved = sieve(10_000_000)
    val safe = IntArray(35)
    var count = 0
    var i = 3
    while (count < 35) {
        if (!sieved[i] && !sieved[(i - 1) / 2]) safe[count++] = i
        i += 2
    }
    println("The first 35 safe primes are:")
    println(safe.joinToString(" ","[", "]\n"))

    count = 0
    for (j in 3 until 1_000_000 step 2) {
        if (!sieved[j] && !sieved[(j - 1) / 2]) count++
    }
    System.out.printf("The number of safe primes below 1,000,000 is %,d\n\n", count)

    for (j in 1_000_001 until 10_000_000 step 2) {
        if (!sieved[j] && !sieved[(j - 1) / 2]) count++
    }
    System.out.printf("The number of safe primes below 10,000,000 is %,d\n\n", count)

    val unsafe = IntArray(40)
    unsafe[0] = 2  // since (2 - 1)/2 is not prime
    count = 1
    i = 3
    while (count < 40) {
        if (!sieved[i] && sieved[(i - 1) / 2]) unsafe[count++] = i
        i += 2
    }
    println("The first 40 unsafe primes are:")
    println(unsafe.joinToString(" ","[", "]\n"))

    count = 1
    for (j in 3 until 1_000_000 step 2) {
        if (!sieved[j] && sieved[(j - 1) / 2]) count++
    }
    System.out.printf("The number of unsafe primes below 1,000,000 is %,d\n\n", count)

    for (j in 1_000_001 until 10_000_000 step 2) {
        if (!sieved[j] && sieved[(j - 1) / 2]) count++
    }
    System.out.printf("The number of unsafe primes below 10,000,000 is %,d\n\n", count)
}
Output:
The first 35 safe primes are:
[5 7 11 23 47 59 83 107 167 179 227 263 347 359 383 467 479 503 563 587 719 839 863 887 983 1019 1187 1283 1307 1319 1367 1439 1487 1523 1619]

The number of safe primes below 1,000,000 is 4,324

The number of safe primes below 10,000,000 is 30,657

The first 40 unsafe primes are:
[2 3 13 17 19 29 31 37 41 43 53 61 67 71 73 79 89 97 101 103 109 113 127 131 137 139 149 151 157 163 173 181 191 193 197 199 211 223 229 233]

The number of unsafe primes below 1,000,000 is 74,174

The number of unsafe primes below 10,000,000 is 633,922

Ksh[edit]

#!/bin/ksh

# Safe primes and unsafe primes

#	# Variables:
#
integer safecnt=0 safedisp=35 safecnt1M=0
integer unsacnt=0 unsadisp=40 unsacnt1M=0
typeset -a safeprime unsafeprime

#	# Functions:
#

#	# Function _isprime(n) return 1 for prime, 0 for not prime
#
function _isprime {
	typeset _n ; integer _n=$1
	typeset _i ; integer _i

	(( _n < 2 )) && return 0
	for (( _i=2 ; _i*_i<=_n ; _i++ )); do
		(( ! ( _n % _i ) )) && return 0
	done
	return 1
}

#	# Function _issafe(p) return 1 for safe prime, 0 for not
#
function _issafe {
	typeset _p ; integer _p=$1

	_isprime $(( (_p - 1) / 2 ))
	return $?
}

 ######
# main #
 ######

for ((n=3; n<=10000000; n++)); do
	_isprime ${n}
	(( ! $? )) && continue
	_issafe ${n}
	if (( $? )); then
		(( safecnt++ ))
		(( safecnt < safedisp)) && safeprime+=( ${n} )
		(( n <= 999999 )) && safecnt1M=${safecnt}
	else
		(( unsacnt++ ))
		(( unsacnt < unsadisp)) && unsafeprime+=( ${n} )
		(( n <= 999999 )) && unsacnt1M=${unsacnt}
	fi
done

print "Safe primes:\n${safeprime[*]}"
print "There are ${safecnt1M} under 1,000,000"
print "There are ${safecnt} under 10,000,000\n"

print "Unsafe primes:\n${unsafeprime[*]}"
print "There are ${unsacnt1M} under 1,000,000"
print "There are ${unsacnt} under 10,000,000"
Output:

Safe primes: 5 7 11 23 47 59 83 107 167 179 227 263 347 359 383 467 479 503 563 587 719 839 863 887 983 1019 1187 1283 1307 1319 1367 1439 1487 1523 1619 There are 4324 under 1,000,000 There are 30657 under 10,000,000 Unsafe primes: 3 13 17 19 29 31 37 41 43 53 61 67 71 73 79 89 97 101 103 109 113 127 131 137 139 149 151 157 163 173 181 191 193 197 199 211 223 229 233 There are 74173 under 1,000,000

There are 633921 under 10,000,000

Lua[edit]

-- FUNCS:
local function T(t) return setmetatable(t, {__index=table}) end
table.filter = function(t,f) local s=T{} for _,v in ipairs(t) do if f(v) then s[#s+1]=v end end return s end
table.map = function(t,f,...) local s=T{} for _,v in ipairs(t) do s[#s+1]=f(v,...) end return s end
table.firstn = function(t,n) local s=T{} n=n>#t and #t or n for i = 1,n do s[i]=t[i] end return s end

-- SIEVE:
local sieve, safe, unsafe, floor, N = {}, T{}, T{}, math.floor, 10000000
for i = 2,N do sieve[i]=true end
for i = 2,N do if sieve[i] then for j=i*i,N,i do sieve[j]=nil end end end
for i = 2,N do if sieve[i] then local t=sieve[floor((i-1)/2)] and safe or unsafe t[#t+1]=i end end

-- TASKS:
local function commafy(i) return tostring(i):reverse():gsub("(%d%d%d)","%1,"):reverse():gsub("^,","") end
print("First 35 safe primes        :  " .. safe:firstn(35):map(commafy):concat(" "))
print("# safe primes < 1,000,000   :  " .. commafy(#safe:filter(function(v) return v<1e6 end)))
print("# safe primes < 10,000,000  :  " .. commafy(#safe))
print("First 40 unsafe primes      :  " .. unsafe:firstn(40):map(commafy):concat(" "))
print("# unsafe primes < 1,000,000 :  " .. commafy(#unsafe:filter(function(v) return v<1e6 end)))
print("# unsafe primes < 10,000,000:  " .. commafy(#unsafe))
Output:
First 35 safe primes        :  5 7 11 23 47 59 83 107 167 179 227 263 347 359 383 467 479 503 563 587 719 839 863 887 983 1,019 1,187 1,283 1,307 1,319 1,367 1,439 1,487 1,523 1,619
# safe primes < 1,000,000   :  4,324
# safe primes < 10,000,000  :  30,657
First 40 unsafe primes      :  2 3 13 17 19 29 31 37 41 43 53 61 67 71 73 79 89 97 101 103 109 113 127 131 137 139 149 151 157 163 173 181 191 193 197 199 211 223 229 233
# unsafe primes < 1,000,000 :  74,174
# unsafe primes < 10,000,000:  633,922

Maple[edit]

showSafePrimes := proc(n::posint) 
local prime_list, k; 
prime_list := [5]; 
for k to n - 1 do 
  prime_list := [op(prime_list), NumberTheory:-NextSafePrime(prime_list[-1])]; 
end do; 
return prime_list; 
end proc;

showUnsafePrimes := proc(n::posint)
local prime_num, k;
prime_num := [2];
for k to n-1 do
  prime_num := [op(prime_num), nextprime(prime_num[-1])];
end do;
return remove(x -> member(x, showSafePrimes(n)), prime_num);
end proc:

countSafePrimes := proc(n::posint) 
local counts, prime; 
counts := 0; 
prime := 5; 
while prime < n do prime := NumberTheory:-NextSafePrime(prime); 
  counts := counts + 1; 
end do; 
return counts; 
end proc;

countUnsafePrimes := proc(n::posint)
local safe_counts, total; 
safe_counts := countSafePrimes(n); 
total := NumberTheory:-PrimeCounting(n); 
return total - safe_counts; 
end proc;

showSafePrimes(35);
showUnsafePrimes(40);
countSafePrimes(1000000);                        
countSafePrimes(10000000);
countUnsafePrimes(1000000);
countUnsafePrimes(10000000);
Output:
[5, 7, 11, 23, 47, 59, 83, 107, 167, 179, 227, 263, 347, 359, 383, 467, 479, 503, 563, 587, 719, 839, 863, 887, 983, 1019, 1187, 1283, 1307, 1319, 1367, 1439, 1487, 1523, 1619]
[2, 3, 13, 17, 19, 29, 31, 37, 41, 43, 53, 61, 67, 71, 73, 79, 89, 97, 101, 103, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 173]
4324
30657
74174
633922

Mathematica/Wolfram Language[edit]

ClearAll[SafePrimeQ, UnsafePrimeQ]
SafePrimeQ[n_Integer] := PrimeQ[n] \[And] PrimeQ[(n - 1)/2]
UnsafePrimeQ[n_Integer] := PrimeQ[n] \[And] ! PrimeQ[(n - 1)/2]

res = {};
i = 1;
While[Length[res] < 35,
 test = SafePrimeQ[Prime[i]];
 If[test, AppendTo[res, Prime[i]]];
 i++
 ]
res

Count[Range[PrimePi[10^6]], _?(Prime /* SafePrimeQ)]
Count[Range[PrimePi[10^7]], _?(Prime /* SafePrimeQ)]

res = {};
i = 1;
While[Length[res] < 40,
 test = UnsafePrimeQ[Prime[i]];
 If[test, AppendTo[res, Prime[i]]];
 i++
 ]
res

Count[Range[PrimePi[10^6]], _?(Prime /* UnsafePrimeQ)]
Count[Range[PrimePi[10^7]], _?(Prime /* UnsafePrimeQ)]
Output:
{5,7,11,23,47,59,83,107,167,179,227,263,347,359,383,467,479,503,563,587,719,839,863,887,983,1019,1187,1283,1307,1319,1367,1439,1487,1523,1619}
4324
30657
{2,3,13,17,19,29,31,37,41,43,53,61,67,71,73,79,89,97,101,103,109,113,127,131,137,139,149,151,157,163,173,181,191,193,197,199,211,223,229,233}
74174
633922

Nim[edit]

import sequtils, strutils

const N = 10_000_000

# Erathostene's Sieve. Only odd values are represented. False value means prime.
var sieve: array[N div 2 + 1, bool]
sieve[0] = true   # 1 is not prime.

for i in 1..sieve.high:
  if not sieve[i]:
    let n = 2 * i + 1
    for k in countup(n * n, N, 2 * n):
      sieve[k shr 1] = true


proc isprime(n: Positive): bool =
  ## Check if a number is prime.
  n == 2 or (n and 1) != 0 and not sieve[n shr 1]


proc classifyPrimes(): tuple[safe, unsafe: seq[int]] =
  ## Classify prime numbers in safe and unsafe numbers.
  for n in 2..N:
    if n.isprime():
      if (n shr 1).isprime():
        result[0].add n
      else:
        result[1].add n

when isMainModule:

  let (safe, unsafe) = classifyPrimes()

  echo "First 35 safe primes:"
  echo safe[0..<35].join(" ")
  echo "Count of safe primes below  1_000_000:",
      ($safe.filterIt(it < 1_000_000).len).insertSep(',').align(7)
  echo "Count of safe primes below 10_000_000:",
      ($safe.filterIt(it < 10_000_000).len).insertSep(',').align(7)

  echo "First 40 unsafe primes:"
  echo unsafe[0..<40].join(" ")
  echo "Count of unsafe primes below  1_000_000:",
      ($unsafe.filterIt(it < 1_000_000).len).insertSep(',').align(8)
  echo "Count of unsafe primes below 10_000_000:",
      ($unsafe.filterIt(it < 10_000_000).len).insertSep(',').align(8)
Output:
First 35 safe primes:
5 7 11 23 47 59 83 107 167 179 227 263 347 359 383 467 479 503 563 587 719 839 863 887 983 1019 1187 1283 1307 1319 1367 1439 1487 1523 1619
Count of safe primes below  1_000_000:  4,324
Count of safe primes below 10_000_000: 30,657
First 40 unsafe primes:
2 3 13 17 19 29 31 37 41 43 53 61 67 71 73 79 89 97 101 103 109 113 127 131 137 139 149 151 157 163 173 181 191 193 197 199 211 223 229 233
Count of unsafe primes below  1_000_000:  74,174
Count of unsafe primes below 10_000_000: 633,922

Pascal[edit]

Works with: Free Pascal

Using unit mp_prime of Wolfgang Erhardt ( RIP ) , of which I use two sieve, to simplify things. Generating small primes and checked by the second, which starts to run 2x ahead.Sieving of consecutive prime number is much faster than primality check.

program Sophie;
{ Find and count Sophie Germain primes }
{ uses unit mp_prime out of mparith of Wolfgang Ehrhardt
* http://wolfgang-ehrhardt.de/misc_en.html#mparith
  http://wolfgang-ehrhardt.de/mp_intro.html }
{$APPTYPE CONSOLE}
uses
 mp_prime,sysutils; 
var
  pS0,pS1:TSieve;  
procedure SafeOrNoSavePrimeOut(totCnt:NativeInt;CntSafe:boolean);
var
  cnt,pr,pSG,testPr : NativeUint;
begin
  prime_sieve_reset(pS0,1);
  prime_sieve_reset(pS1,1);
  cnt := 0;
// memorize prime of the sieve, because sometimes prime_sieve_next(pS1) is to far ahead.
  testPr := prime_sieve_next(pS1);
  IF CntSafe then  
  Begin
    writeln('First ',totCnt,' safe primes');  
    repeat
      pr := prime_sieve_next(pS0);
      pSG := 2*pr+1;
      while testPr< pSG do
        testPr := prime_sieve_next(pS1);
      if pSG = testPr then
      begin
        write(pSG,',');
        inc(cnt);
      end; 
    until cnt >= totCnt
  end  
  else
  Begin
    writeln('First ',totCnt,' unsafe primes');  
    repeat
      pr := prime_sieve_next(pS0);
      pSG := (pr-1) DIV 2;
      while testPr< pSG do
        testPr := prime_sieve_next(pS1);
      if pSG <> testPr then
      begin
        write(pr,',');
        inc(cnt);
      end; 
    until cnt >= totCnt; 
  end;  
  writeln(#8,#32);  
end; 

function CountSafePrimes(Limit:NativeInt):NativeUint;
var
  cnt,pr,pSG,testPr : NativeUint;
begin
  prime_sieve_reset(pS0,1);
  prime_sieve_reset(pS1,1);
  cnt := 0;
  testPr := 0;
  repeat
    pr := prime_sieve_next(pS0);
    pSG := 2*pr+1;
    while testPr< pSG do
      testPr := prime_sieve_next(pS1);
    if pSG = testPr then
      inc(cnt);
  until pSG >= Limit; 
  CountSafePrimes := cnt;
end; 

procedure CountSafePrimesOut(Limit:NativeUint);
Begin
  writeln('there are ',CountSafePrimes(limit),' safe primes out of ',
          primepi32(limit),' primes up to ',Limit);
end;

procedure CountUnSafePrimesOut(Limit:NativeUint);
var
  prCnt: NativeUint;
Begin
  prCnt := primepi32(limit);
  writeln('there are ',prCnt-CountSafePrimes(limit),' unsafe primes out of ',
          prCnt,' primes up to ',Limit);
end;

var
  T1,T0 : INt64;
begin
  T0 :=gettickcount64; 
  prime_sieve_init(pS0,1);
  prime_sieve_init(pS1,1);
//Find and display (on one line) the first  35  safe primes.  
  SafeOrNoSavePrimeOut(35,true);
//Find and display the  count  of the safe primes below  1,000,000. 
  CountSafePrimesOut(1000*1000);
//Find and display the  count  of the safe primes below 10,000,000.  
  CountSafePrimesOut(10*1000*1000);  
//Find and display (on one line) the first  40  unsafe primes.  
  SafeOrNoSavePrimeOut(40,false);
//Find and display the  count  of the unsafe primes below  1,000,000.
  CountUnSafePrimesOut(1000*1000);
//Find and display the  count  of the unsafe primes below 10,000,000.  
  CountUnSafePrimesOut(10*1000*1000);
  writeln;
  CountSafePrimesOut(1000*1000*1000);        
  T1 :=gettickcount64; 
  writeln('runtime ',T1-T0,' ms');
end.
Output:
First 35 safe primes
5,7,11,23,47,59,83,107,167,179,227,263,347,359,383,467,479,503,563,587,719,839,863,887,983,1019,1187,1283,1307,1319,1367,1439,1487,1523,1619
there are 4324 safe primes out of 78498 primes up to 1000000
there are 30657 safe primes out of 664579 primes up to 10000000
First 40 unsafe primes
2,3,13,17,19,29,31,37,41,43,53,61,67,71,73,79,89,97,101,103,109,113,127,131,137,139,149,151,157,163,173,181,191,193,197,199,211,223,229,233
there are 74174 unsafe primes out of 78498 primes up to 1000000
there are 633922 unsafe primes out of 664579 primes up to 10000000
there are 1775676 safe primes out of 50847534 primes up to 1000000000
runtime 2797 ms

Perl[edit]

The module ntheory does fast prime generation and testing.

Library: ntheory
use ntheory qw(forprimes is_prime);

my $upto = 1e7;
my %class = ( safe => [], unsafe => [2] );

forprimes {
    push @{$class{ is_prime(($_-1)>>1) ? 'safe' : 'unsafe' }}, $_;
} 3, $upto;

for (['safe', 35], ['unsafe', 40]) {
    my($type, $quantity) = @$_;
    print  "The first $quantity $type primes are:\n";
    print join(" ", map { comma($class{$type}->[$_-1]) } 1..$quantity), "\n";
    for my $q ($upto/10, $upto) {
        my $n = scalar(grep { $_ <= $q } @{$class{$type}});
        printf "The number of $type primes up to %s: %s\n", comma($q), comma($n);
    }
}

sub comma {
    (my $s = reverse shift) =~ s/(.{3})/$1,/g;
    $s =~ s/,(-?)$/$1/;
    $s = reverse $s;
}
Output:
The first 35 safe primes are:
5 7 11 23 47 59 83 107 167 179 227 263 347 359 383 467 479 503 563 587 719 839 863 887 983 1,019 1,187 1,283 1,307 1,319 1,367 1,439 1,487 1,523 1,619
The number of safe primes up to 1,000,000: 4,324
The number of safe primes up to 10,000,000: 30,657
The first 40 unsafe primes are:
2 3 13 17 19 29 31 37 41 43 53 61 67 71 73 79 89 97 101 103 109 113 127 131 137 139 149 151 157 163 173 181 191 193 197 199 211 223 229 233
The number of unsafe primes up to 1,000,000: 74,174
The number of unsafe primes up to 10,000,000: 633,922

Phix[edit]

with javascript_semantics
sequence safe = {}, unsafe = {}
function filter_range(integer lo, hi)
    while true do
        integer p = get_prime(lo)
        if p>hi then return lo end if
        if p>2 and is_prime((p-1)/2) then
            safe &= p
        else
            unsafe &= p
        end if
        lo += 1
    end while
end function
integer lo = filter_range(1,1_000_000),
        ls = length(safe),
        lu = length(unsafe)
{} = filter_range(lo,10_000_000)
printf(1,"The first 35 safe primes: %v\n",{safe[1..35]})
printf(1,"Count of safe primes below 1,000,000: %,d\n",ls)
printf(1,"Count of safe primes below 10,000,000: %,d\n",length(safe))
printf(1,"The first 40 unsafe primes: %v\n",{unsafe[1..40]})
printf(1,"Count of unsafe primes below 1,000,000: %,d\n",lu)
printf(1,"Count of unsafe primes below 10,000,000: %,d\n",length(unsafe))
Output:
The first 35 safe primes: {5,7,11,23,47,59,83,107,167,179,227,263,347,359,383,467,479,503,563,587,719,839,863,887,983,1019,1187,1283,1307,1319,1367,1439,1487,1523,1619}
Count of safe primes below 1,000,000: 4,324
Count of safe primes below 10,000,000: 30,657
The first 40 unsafe primes: {2,3,13,17,19,29,31,37,41,43,53,61,67,71,73,79,89,97,101,103,109,113,127,131,137,139,149,151,157,163,173,181,191,193,197,199,211,223,229,233}
Count of unsafe primes below 1,000,000: 74,174
Count of unsafe primes below 10,000,000: 633,922

PureBasic[edit]

#MAX=10000000
Global Dim P.b(#MAX) : FillMemory(@P(),#MAX,1,#PB_Byte)
Global NewList Primes.i()
Global NewList SaveP.i()
Global NewList UnSaveP.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

ForEach Primes()
  If P((Primes()-1)/2) And Primes()>3 : AddElement(SaveP()) : SaveP()=Primes() : If Primes()<1000000 : c1+1 : EndIf
  Else 
    AddElement(UnSaveP()) : UnSaveP()=Primes() : If Primes()<1000000 : c2+1 : EndIf
  EndIf
Next

OpenConsole()
PrintN("First 35 safe primes:")
If FirstElement(SaveP())
  For i=1 To 35 : Print(Str(SaveP())+" ") : NextElement(SaveP()) : Next
EndIf
PrintN(~"\nThere are "+FormatNumber(c1,0,".","'")+" safe primes below 1'000'000")
PrintN("There are "+FormatNumber(ListSize(SaveP()),0,".","'")+" safe primes below 10'000'000")
PrintN("")
PrintN("First 40 unsafe primes:")
If FirstElement(UnSaveP())
  For i=1 To 40 : Print(Str(UnSaveP())+" ") : NextElement(UnSaveP()) : Next
EndIf
PrintN(~"\nThere are "+FormatNumber(c2,0,".","'")+" unsafe primes below 1'000'000")
PrintN("There are "+FormatNumber(ListSize(UnSaveP()),0,".","'")+" unsafe primes below 10'000'000")
Input()
Output:
First 35 safe primes:
5 7 11 23 47 59 83 107 167 179 227 263 347 359 383 467 479 503 563 587 719 839 863 887 983 1019 1187 1283 1307 1319 1367 1439 1487 1523 1619 
There are 4'324 safe primes below 1'000'000
There are 30'657 safe primes below 10'000'000

First 40 unsafe primes:
2 3 13 17 19 29 31 37 41 43 53 61 67 71 73 79 89 97 101 103 109 113 127 131 137 139 149 151 157 163 173 181 191 193 197 199 211 223 229 233 
There are 74'174 unsafe primes below 1'000'000
There are 633'922 unsafe primes below 10'000'000

Python[edit]

primes =[]
sp =[]
usp=[]
n = 10000000
if 2<n:
    primes.append(2)
for i in range(3,n+1,2):
    for j in primes:
        if(j>i/2) or (j==primes[-1]):
            primes.append(i)
            if((i-1)/2) in primes:
                sp.append(i)
                break
            else:
                usp.append(i)
                break
        if (i%j==0):
            break

print('First 35 safe primes are:\n' , sp[:35])
print('There are '+str(len(sp[:1000000]))+' safe primes below 1,000,000')
print('There are '+str(len(sp))+' safe primes below 10,000,000')
print('First 40 unsafe primes:\n',usp[:40])
print('There are '+str(len(usp[:1000000]))+' unsafe primes below 1,000,000')
print('There are '+str(len(usp))+' safe primes below 10,000,000')
Output:
First 35 safe primes: 
[5,7,11,23,47,59,83,107,167,179,227,263,347,359,383,467,479,503,563,587,719,839,863,887,983,1019,1187,1283,1307,1319,1367,1439,1487,1523,1619]
There are 4,234 safe primes below 1,000,000
There are 30,657 safe primes below 10,000,000
First 40 unsafe primes: 
[2,3,13,17,19,29,31,37,41,43,53,61,67,71,73,79,89,97,101,103,109,113,127,131,137,139,149,151,157,163,173,181,191,193,197,199,211,223,229,233]
There are 74,174 unsafe primes below 1,000,000
There are 633,922 unsafe primes below 10,000,000

Raku[edit]

(formerly Perl 6)

Works with: Rakudo version 2018.08

Raku has a built-in method .is-prime to test for prime numbers. It's great for testing individual numbers or to find/filter a few thousand numbers, but when you are looking for millions, it becomes a drag. No fear, the Raku ecosystem has a fast prime sieve module available which can produce 10 million primes in a few seconds. Once we have the primes, it is just a small matter of filtering and formatting them appropriately.

sub comma { $^i.flip.comb(3).join(',').flip }

use Math::Primesieve;

my $sieve = Math::Primesieve.new;

my @primes = $sieve.primes(10_000_000);

my %filter = @primes.Set;

my $primes = @primes.classify: { %filter{($_ - 1)/2} ?? 'safe' !! 'unsafe' };

for 'safe', 35, 'unsafe', 40 -> $type, $quantity {
    say "The first $quantity $type primes are:";

    say $primes{$type}[^$quantity]».&comma;

    say "The number of $type primes up to {comma $_}: ",
    comma $primes{$type}.first(* > $_, :k) // +$primes{$type} for 1e6, 1e7;

    say '';
}
Output:
The first 35 safe primes are:
(5 7 11 23 47 59 83 107 167 179 227 263 347 359 383 467 479 503 563 587 719 839 863 887 983 1,019 1,187 1,283 1,307 1,319 1,367 1,439 1,487 1,523 1,619)
The number of safe primes up to 1,000,000: 4,324
The number of safe primes up to 10,000,000: 30,657

The first 40 unsafe primes are:
(2 3 13 17 19 29 31 37 41 43 53 61 67 71 73 79 89 97 101 103 109 113 127 131 137 139 149 151 157 163 173 181 191 193 197 199 211 223 229 233)
The number of unsafe primes up to 1,000,000: 74,174
The number of unsafe primes up to 10,000,000: 633,922

REXX[edit]

/*REXX program lists a sequence  (or a count)  of  ──safe──   or   ──unsafe──   primes. */
parse arg N kind _ . 1 . okind;     upper kind   /*obtain optional arguments from the CL*/
if N=='' | N==","  then N= 35                    /*Not specified?   Then assume default.*/
if kind=='' | kind==","  then kind= 'SAFE'       /* "      "          "     "      "    */
if _\==''                             then call ser 'too many arguments specified.'
if kind\=='SAFE'  &  kind\=='UNSAFE'  then call ser 'invalid 2nd argument: '   okind
if kind =='UNSAFE'  then safe= 0;  else safe= 1  /*SAFE  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;    #= 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=1  for #   while lim<=N;  j= !.i    /* [↓]  find primes, and maybe show 'em*/
        call safeUnsafe;      $= 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 safeUnsafe                               /*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 & j>N  then do; lim= j; m= m-1; end; else call app; return 1
app: if tell  then if length($ j)>w  then do;  say $; $ =j;   end; else $= $ j;   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 _
/*──────────────────────────────────────────────────────────────────────────────────────*/
safeUnsafe: ?= (j-1) % 2                         /*obtain the other part of KIND prime. */
            if safe  then if @.? == ''  then return 0             /*not a    safe prime.*/
                                        else return add()         /*is  "      "    "   */
                     else if @.? == ''  then return add()         /*is  an unsafe prime.*/
                                        else return 0             /*not  "   "      "   */

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:     35

Shown at   5/6   size.)

5 7 11 23 47 59 83 107 167 179 227 263 347 359 383 467 479 503 563 587 719 839 863 887 983 1019 1187 1283 1307 1319 1367 1439 1487 1523 1619

35  SAFE primes found.
output   when using the input:     -1000000
4,324  SAFE primes found below or equal to  1,000,000.
output   when using the input:     -10000000
30,657  SAFE primes found below or equal to  10,000,000.
output   when using the input:     40   unsafe

(Shown at   5/6   size.)

2 3 13 17 19 29 31 37 41 43 53 61 67 71 73 79 89 97 101 103 109 113 127 131 137 139 149 151 157 163 173 181 191 193 197 199 211 223 229 233

40  UNSAFE primes found.
output   when using the input:     -1000000   unsafe
74,174  UNSAFE primes found below or equal to  1,000,000.
output   when using the input:     -10000000
633,922  UNSAFE primes found below or equal to  10,000,000.

Ring[edit]

load "stdlib.ring"

see "working..." + nl

p = 1
num = 0
limit1 = 36
limit2 = 41
safe1 = 1000000
safe2 = 10000000

see "the first 35 Safeprimes are: " + nl
while true 
      p = p + 1
      p2 = (p-1)/2
      if isprime(p) and isprime(p2)
         num = num + 1
         if num < limit1
            see " " + p
         else
            exit
         ok
      ok
end

see nl + "the first 40 Unsafeprimes are: " + nl
p = 1
num = 0
while true 
      p = p + 1
      p2 = (p-1)/2
      if isprime(p) and not isprime(p2)
         num = num + 1
         if num < limit2
            see " " + p
         else
            exit
         ok
      ok
end

p = 1
num1 = 0
num2 = 0
while true 
      p = p + 1
      p2 = (p-1)/2
      if isprime(p) and isprime(p2)
         if p < safe1
            num1 = num1 + 1
         ok
         if p < safe2
            num2 = num2 + 1
         else
            exit
         ok
      ok
end

see nl + "safe primes below 1,000,000: " + num1 + nl
see "safe primes below 10,000,000: " + num2 + nl

p = 1
num1 = 0
num2 = 0
while true 
      p = p + 1
      p2 = (p-1)/2
      if isprime(p) and not isprime(p2)
         if p < safe1
            num1 = num1 + 1
         ok
         if p < safe2
            num2 = num2 + 1
         else
            exit
         ok
      ok
end

see "unsafe primes below 1,000,000: " + num1 + nl
see "unsafe primes below 10,000,000: " + num2 + nl

see "done..." + nl

Output:

working...
the first 35 Safeprimes are:
5 7 11 23 47 59 83 107 167 179 227 263 347 359 383 467 479 503 563 587 719 839 863 887 983 1019 1187 1283 1307 1319 1367 1439 1487 1523 1619
the first 40 Unsafeprimes are:
2 3 13 17 19 29 31 37 41 43 53 61 67 71 73 79 89 97 101 103 109 113 127 131 137 139 149 151 157 163 173 181 191 193 197 199 211 223 229 233
safe primes below 1,000,000: 4324
safe primes below 10,000,000: 30657
unsafe primes below 1,000,000: 74174
unsafe primes below 10,000,000: 633922
done...


Ruby[edit]

require "prime"
class Integer
  def safe_prime? #assumes prime
    ((self-1)/2).prime?
  end
end

def format_parts(n)
  partitions = Prime.each(n).partition(&:safe_prime?).map(&:count)
  "There are %d safes and %d unsafes below #{n}."% partitions
end

puts "First 35 safe-primes:"
p Prime.each.lazy.select(&:safe_prime?).take(35).to_a
puts format_parts(1_000_000), "\n" 

puts "First 40 unsafe-primes:"
p Prime.each.lazy.reject(&:safe_prime?).take(40).to_a
puts format_parts(10_000_000)
Output:
First 35 safe-primes:
[5, 7, 11, 23, 47, 59, 83, 107, 167, 179, 227, 263, 347, 359, 383, 467, 479, 503, 563, 587, 719, 839, 863, 887, 983, 1019, 1187, 1283, 1307, 1319, 1367, 1439, 1487, 1523, 1619]
There are 4324 safes and 74174 unsafes below 1000000.

First 40 unsafe-primes:
[2, 3, 13, 17, 19, 29, 31, 37, 41, 43, 53, 61, 67, 71, 73, 79, 89, 97, 101, 103, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 173, 181, 191, 193, 197, 199, 211, 223, 229, 233]
There are 30657 safes and 633922 unsafes below 10000000.

Rust[edit]

fn is_prime(n: i32) -> bool {
	for i in 2..n {
		if i * i > n {
			return true;
		}
		if n % i == 0 {
			return false;
		}
	}
	n > 1
}

fn is_safe_prime(n: i32) -> bool {
	is_prime(n) && is_prime((n - 1) / 2)
}

fn is_unsafe_prime(n: i32) -> bool {
	is_prime(n) && !is_prime((n - 1) / 2)
}

fn next_prime(n: i32) -> i32 {
	for i in (n+1).. {
		if is_prime(i) {
			return i;
		}
	}
	0
}

fn main() {
	let mut safe = 0;
	let mut unsf = 0;
	let mut p = 2;

	print!("first 35 safe primes: ");
	while safe < 35 {
		if is_safe_prime(p) {
			safe += 1;
			print!("{} ", p);
		}
		p = next_prime(p);
	}
	println!("");

	p = 2;

	print!("first 35 unsafe primes: ");
	while unsf < 35 {
		if is_unsafe_prime(p) {
			unsf += 1;
			print!("{} ", p);
		}
		p = next_prime(p);
	}
	println!("");

	p = 2;
	safe = 0;
	unsf = 0;

	while p < 1000000 {
		if is_safe_prime(p) {
			safe += 1;
		} else {
			unsf += 1;
		}
		p = next_prime(p);
	}
	println!("safe primes below 1,000,000: {}", safe);
	println!("unsafe primes below 1,000,000: {}", unsf);

	while p < 10000000 {
		if is_safe_prime(p) {
			safe += 1;
		} else {
			unsf += 1;
		}
		p = next_prime(p);
	}
	println!("safe primes below 10,000,000: {}", safe);
	println!("unsafe primes below 10,000,000: {}", unsf);
}
first 35 safe primes: 5 7 11 23 47 59 83 107 167 179 227 263 347 359 383 467 479 503 563 587 719 839 863 887 983 1019 1187 1283 1307 1319 1367 1439 1487 1523 1619
first 35 unsafe primes: 2 3 13 17 19 29 31 37 41 43 53 61 67 71 73 79 89 97 101 103 109 113 127 131 137 139 149 151 157 163 173 181 191 193 197
safe primes below 1,000,000: 4324
unsafe primes below 1,000,000: 74174
safe primes below 10,000,000: 30657
unsafe primes below 10,000,000: 633922

Shale[edit]

#!/usr/local/bin/shale

// Safe and unsafe primes.
//
// Safe prime p: (p - 1) / 2 is prime
// Unsafe prime: any prime that is not a safe prime

primes library

init dup var {
  pl sieve type primes::()
  10000000 0 pl generate primes::()
} =

isSafe dup var {
  1 - 2 / pl isprime primes::()
} =

comma dup var {
  n dup var swap =
  t dup var n 1000 / =
  b dup var n 1000 % =

  t 0 == {
    b print
  } {
    t.value comma() b ",%03d" printf
  } if
} =

go dup var {
  n var
  c1 var
  c10 var
  i var
  p var

  "The first 35 safe primes are:" print
  n 0 =
  c1 0 =
  c10 0 =
  i 0 =
  { i count pl:: < } {
    p i pl get primes::() =
    p isSafe() {
      n 35 < {
        p " %d" printf
        n++
        n 35 == { "" println } ifthen
      } ifthen

      p 1000000 < { c1++ } ifthen

      c10++
    } ifthen

    i++
  } while
  "Number of safe primes below  1,000,000 is " print c1.value comma() "" println
  "Number of safe primes below 10,000,000 is " print c10.value comma() "" println

  "The first 40 unsafe primes are:" print
  n 0 =
  c1 0 =
  c10 0 =
  i 0 =
  { i count pl:: < } {
    p i pl get primes::() =
    p isSafe() not {
      n 40 < {
        p " %d" printf
        n++
        n 40 == { "" println } ifthen
      } ifthen

      p 1000000 < { c1++ } ifthen

      c10++
    } ifthen

    i++
  } while
  "Number of unsafe primes below  1,000,000 is " print c1.value comma() "" println
  "Number of unsafe primes below 10,000,000 is " print c10.value comma() "" println
} =

init()
go()
Output:
The first 35 safe primes are: 5 7 11 23 47 59 83 107 167 179 227 263 347 359 383 467 479 503 563 587 719 839 863 887 983 1019 1187 1283 1307 1319 1367 1439 1487 1523 1619
Number of safe primes below  1,000,000 is 4,324
Number of safe primes below 10,000,000 is 30,657
The first 40 unsafe primes are: 2 3 13 17 19 29 31 37 41 43 53 61 67 71 73 79 89 97 101 103 109 113 127 131 137 139 149 151 157 163 173 181 191 193 197 199 211 223 229 233
Number of unsafe primes below  1,000,000 is 74,174
Number of unsafe primes below 10,000,000 is 633,922

Sidef[edit]

func is_safeprime(p) {
    is_prime(p) && is_prime((p-1)/2)
}

func is_unsafeprime(p) {
    is_prime(p) && !is_prime((p-1)/2)
}

func safeprime_count(from, to) {
    from..to -> count_by(is_safeprime)
}

func unsafeprime_count(from, to) {
    from..to -> count_by(is_unsafeprime)
}

say "First 35 safe-primes:"
say (1..Inf -> lazy.grep(is_safeprime).first(35).join(' '))
say ''
say "First 40 unsafe-primes:"
say (1..Inf -> lazy.grep(is_unsafeprime).first(40).join(' '))
say ''
say "There are #{safeprime_count(1, 1e6)} safe-primes bellow 10^6"
say "There are #{unsafeprime_count(1, 1e6)} unsafe-primes bellow 10^6"
say ''
say "There are #{safeprime_count(1, 1e7)} safe-primes bellow 10^7"
say "There are #{unsafeprime_count(1, 1e7)} unsafe-primes bellow 10^7"
Output:
First 35 safe-primes:
5 7 11 23 47 59 83 107 167 179 227 263 347 359 383 467 479 503 563 587 719 839 863 887 983 1019 1187 1283 1307 1319 1367 1439 1487 1523 1619

First 40 unsafe-primes:
2 3 13 17 19 29 31 37 41 43 53 61 67 71 73 79 89 97 101 103 109 113 127 131 137 139 149 151 157 163 173 181 191 193 197 199 211 223 229 233

There are 4324 safe-primes bellow 10^6
There are 74174 unsafe-primes bellow 10^6

There are 30657 safe-primes bellow 10^7
There are 633922 unsafe-primes bellow 10^7

Simula[edit]

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
Output:
THE FIRST 35 SAFE PRIMES ARE:
[5 7 11 23 47 59 83 107 167 179 227 263 347 359 383 467 479 503 563 587 719 839
863 887 983 1019 1187 1283 1307 1319 1367 1439 1487 1523 1619]

THE NUMBER OF SAFE PRIMES BELOW 1,000,000 IS 4324

THE NUMBER OF SAFE PRIMES BELOW 10,000,000 IS 30657

THE FIRST 40 UNSAFE PRIMES ARE:
[2 3 13 17 19 29 31 37 41 43 53 61 67 71 73 79 89 97 101 103 109 113 127 131 137
 139 149 151 157 163 173 181 191 193 197 199 211 223 229 233]

THE NUMBER OF UNSAFE PRIMES BELOW 1,000,000 IS 74174

THE NUMBER OF UNSAFE PRIMES BELOW 10,000,000 IS 633922

Smalltalk[edit]

Works with: Smalltalk/X
[
    | isSafePrime printFirstNElements |
 
    isSafePrime := [:p | ((p-1)//2) isPrime].
    printFirstNElements := 
        [:coll :n | 
            (coll to:n) 
                do:[:p | Transcript show:p] 
                separatedBy:[Transcript space]
        ].
    (Iterator on:[:b | Integer primesUpTo:10000000 do:b])
        partition:isSafePrime
        into:[:savePrimes :unsavePrimes |
            |nSaveBelow1M nSaveBelow10M nUnsaveBelow1M nUnsaveBelow10M|
 
            nSaveBelow1M := savePrimes count:[:p | p < 1000000].
            nSaveBelow10M := savePrimes size.
 
            nUnsaveBelow1M := unsavePrimes count:[:p | p < 1000000].
            nUnsaveBelow10M := unsavePrimes size.
 
            Transcript showCR: 'first 35 safe primes:'.
            printFirstNElements value:savePrimes value:35.
            Transcript cr.
 
            Transcript show: 'safe primes below 1,000,000: '.
            Transcript showCR:nSaveBelow1M printStringWithThousandsSeparator.
 
            Transcript show: 'safe primes below 10,000,000: '.
            Transcript showCR:nSaveBelow10M printStringWithThousandsSeparator.
 
            Transcript showCR: 'first 40 unsafe primes:'.
            printFirstNElements value:unsavePrimes value:40.
            Transcript cr.
 
            Transcript show: 'unsafe primes below 1,000,000: '.
            Transcript showCR:nUnsaveBelow1M printStringWithThousandsSeparator.
 
            Transcript show: 'unsafe primes below 10,000,000: '.
            Transcript showCR:nUnsaveBelow10M printStringWithThousandsSeparator.
        ]
 ] benchmark:'runtime: safe primes'
Output:
first 35 safe primes:
5 7 11 23 47 59 83 107 167 179 227 263 347 359 383 467 479 503 563 587 719 839 863 887 983 1019 1187 1283 1307 1319 1367 1439 1487 1523 1619
safe primes below 1,000,000: 4,324
safe primes below 10,000,000: 30,657
first 40 unsafe primes:
2 3 13 17 19 29 31 37 41 43 53 61 67 71 73 79 89 97 101 103 109 113 127 131 137 139 149 151 157 163 173 181 191 193 197 199 211 223 229 233
unsafe primes below 1,000,000: 74,174
unsafe primes below 10,000,000: 633,922
runtime: safe primes: 996ms

Notes:
1) partition:into: is a method in collection which is a combined select+reject.
2) instead if the Iterator, I could have also used "(Integer primesUpTo:10000000) partition...", but that would use a few additional Mb of temporary memory for the primes collection, whereas the iterator simply computes and enumerates them (without actually collecting them). But, who cares, these days ;-)
3) time is on a 2012 MacBook 2.5Ghz i5; interpreted not jitted. Compiled/jitted time is 738ms.

Swift[edit]

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 safePrimes = PrimeInfo(maxPrint: 35)
var unsafePrimes = PrimeInfo(maxPrint: 40)

let sieve = PrimeSieve(size: limit2)

for prime in 2..<limit2 {
    if sieve.isPrime(number: prime) {
        if sieve.isPrime(number: (prime - 1)/2) {
            safePrimes.addPrime(prime: prime)
        } else {
            unsafePrimes.addPrime(prime: prime)
        }
    }
}

safePrimes.printInfo(name: "safe")
unsafePrimes.printInfo(name: "unsafe")
Output:
First 35 safe primes: [5, 7, 11, 23, 47, 59, 83, 107, 167, 179, 227, 263, 347, 359, 383, 467, 479, 503, 563, 587, 719, 839, 863, 887, 983, 1019, 1187, 1283, 1307, 1319, 1367, 1439, 1487, 1523, 1619]
Number of safe primes below 1,000,000: 4,324
Number of safe primes below 10,000,000: 30,657
First 40 unsafe primes: [2, 3, 13, 17, 19, 29, 31, 37, 41, 43, 53, 61, 67, 71, 73, 79, 89, 97, 101, 103, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 173, 181, 191, 193, 197, 199, 211, 223, 229, 233]
Number of unsafe primes below 1,000,000: 74,174
Number of unsafe primes below 10,000,000: 633,922

Visual Basic .NET[edit]

Translation of: C#
Dependent on using .NET Core 2.1 or 2.0, or .NET Framework 4.7.2
Imports System.Console

Namespace safety
    Module SafePrimes
        Dim pri_HS As HashSet(Of Integer) = Primes(10_000_000).ToHashSet()

        Sub Main()
            For Each UnSafe In {False, True} : Dim n As Integer = If(UnSafe, 40, 35)
                WriteLine($"The first {n} {If(UnSafe, "un", "")}safe primes are:")
                WriteLine(String.Join(" ", pri_HS.Where(Function(p) UnSafe Xor
                                                            pri_HS.Contains(p \ 2)).Take(n)))
            Next : Dim limit As Integer = 1_000_000 : Do
                Dim part = pri_HS.TakeWhile(Function(l) l < limit),
                 sc As Integer = part.Count(Function(p) pri_HS.Contains(p \ 2))
                WriteLine($"Of the primes below {limit:n0}: {sc:n0} are safe, and {part.Count() -
                          sc:n0} are unsafe.") : If limit = 1_000_000 Then limit *= 10 Else Exit Do
            Loop
        End Sub

        Private Iterator Function Primes(ByVal bound As Integer) As IEnumerable(Of Integer)
            If bound < 2 Then Return
            Yield 2
            Dim composite As BitArray = New BitArray((bound - 1) \ 2)
            Dim limit As Integer = (CInt((Math.Sqrt(bound))) - 1) \ 2
            For i As Integer = 0 To limit - 1 : If composite(i) Then Continue For
                Dim prime As Integer = 2 * i + 3 : Yield prime
                Dim j As Integer = (prime * prime - 2) \ 2
                While j < composite.Count : composite(j) = True : j += prime : End While
            Next
            For i As integer = limit To composite.Count - 1 : If Not composite(i) Then Yield 2 * i + 3
            Next
        End Function
    End Module
End Namespace
If not using the latest version of the System.Linq namespace, you can implement the Enumerable.ToHashSet() method by adding
Imports System.Runtime.CompilerServices
to the top and this module inside the safety namespace:
    Module Extensions
        <Extension()>
        Function ToHashSet(Of T)(ByVal src As IEnumerable(Of T), ByVal Optional _
                                 IECmp As IEqualityComparer(Of T) = Nothing) As HashSet(Of T)
            Return New HashSet(Of T)(src, IECmp)
        End Function
    End Module
Output:
The first 35 safe primes are:
5 7 11 23 47 59 83 107 167 179 227 263 347 359 383 467 479 503 563 587 719 839 863 887 983 1019 1187 1283 1307 1319 1367 1439 1487 1523 1619
The first 40 unsafe primes are:
2 3 13 17 19 29 31 37 41 43 53 61 67 71 73 79 89 97 101 103 109 113 127 131 137 139 149 151 157 163 173 181 191 193 197 199 211 223 229 233
Of the primes below 1,000,000: 4,324 are safe, and 74,174 are unsafe.
Of the primes below 10,000,000: 30,657 are safe, and 633,922 are unsafe.

Wren[edit]

Library: Wren-math
Library: Wren-fmt
import "/math" for Int
import "/fmt" for Fmt

var c = Int.primeSieve(1e7, false) // need primes up to 10 million here
var safe = List.filled(35, 0)
var count = 0
var i = 3
while (count < 35) {
    if (!c[i] && !c[(i-1)/2]) {
        safe[count] = i
        count = count + 1
    }
    i = i + 2
}
System.print("The first 35 safe primes are:\n%(safe.join(" "))\n")

count = 35
while (i < 1e6) {
   if (!c[i] && !c[(i-1)/2]) count = count + 1
   i = i + 2
}
Fmt.print("The number of safe primes below 1,000,000 is $,d.\n", count)  

while (i < 1e7) {
   if (!c[i] && !c[(i-1)/2]) count = count + 1
   i = i + 2
}
Fmt.print("The number of safe primes below 10,000,000 is $,d.\n", count)

var unsafe = List.filled(40, 0)
unsafe[0] = 2
count = 1
i = 3
while (count < 40) {
    if (!c[i] && c[(i-1)/2]) {
        unsafe[count] = i
        count = count + 1
    }
    i = i + 2
} 
System.print("The first 40 unsafe primes are:\n%(unsafe.join(" "))\n")

count = 40
while (i < 1e6) {
   if (!c[i] && c[(i-1)/2]) count = count + 1
   i = i + 2
}
Fmt.print("The number of unsafe primes below 1,000,000 is $,d.\n", count)   

while (i < 1e7) {
   if (!c[i] && c[(i-1)/2]) count = count + 1
   i = i + 2
}
Fmt.print("The number of unsafe primes below 10,000,000 is $,d.\n", count)
Output:
The first 35 safe primes are:
5 7 11 23 47 59 83 107 167 179 227 263 347 359 383 467 479 503 563 587 719 839 863 887 983 1019 1187 1283 1307 1319 1367 1439 1487 1523 1619

The number of safe primes below 1,000,000 is 4,324.

The number of safe primes below 10,000,000 is 30,657.

The first 40 unsafe primes are:
2 3 13 17 19 29 31 37 41 43 53 61 67 71 73 79 89 97 101 103 109 113 127 131 137 139 149 151 157 163 173 181 191 193 197 199 211 223 229 233

The number of unsafe primes below 1,000,000 is 74,174.

The number of unsafe primes below 10,000,000 is 633,922.

XPL0[edit]

proc NumOut(Num);       \Output positive integer with commas
int  Num, Dig, Cnt;
[Cnt:= [0];
Num:= Num/10;
Dig:= rem(0);
Cnt(0):= Cnt(0)+1;
if Num then NumOut(Num);
Cnt(0):= Cnt(0)-1;
ChOut(0, Dig+^0);
if rem(Cnt(0)/3)=0 & Cnt(0) then ChOut(0, ^,);
];

func IsPrime(N);        \Return 'true' if N is prime
int  N, I;
[if N <= 2 then return N = 2;
if (N&1) = 0 then \even >2\ return false;
for I:= 3 to sqrt(N) do
    [if rem(N/I) = 0 then return false;
    I:= I+1;
    ];
return true;
];

int  N, SafeCnt, UnsafeCnt Unsafes(40);
[SafeCnt:= 0;  UnsafeCnt:= 0;
Text(0, "First 35 safe primes:^M^J");
for N:= 1 to 10_000_000-1 do
    [if IsPrime(N) then
        [if IsPrime( (N-1)/2 ) then
            [SafeCnt:= SafeCnt+1;
            if SafeCnt <= 35 then
                [NumOut(N);  ChOut(0, ^ )];
            ]
        else
            [Unsafes(UnsafeCnt):= N;
            UnsafeCnt:= UnsafeCnt+1;
            ];
        ];
    if N = 999_999 then
        [Text(0, "^M^JSafe primes below 1,000,000: ");
        NumOut(SafeCnt);
        Text(0, "^M^JUnsafe primes below 1,000,000: ");
        NumOut(UnsafeCnt);
        ];
    ];
Text(0, "^M^JFirst 40 unsafe primes:^M^J");
for N:= 0 to 40-1 do
    [NumOut(Unsafes(N));  ChOut(0, ^ )];
Text(0, "^M^JSafe primes below 10,000,000: ");
NumOut(SafeCnt);
Text(0, "^M^JUnsafe primes below 10,000,000: ");
NumOut(UnsafeCnt);
CrLf(0);
]
Output:
First 35 safe primes:
5 7 11 23 47 59 83 107 167 179 227 263 347 359 383 467 479 503 563 587 719 839 863 887 983 1,019 1,187 1,283 1,307 1,319 1,367 1,439 1,487 1,523 1,619 
Safe primes below 1,000,000: 4,324
Unsafe primes below 1,000,000: 74,174
First 40 unsafe primes:
2 3 13 17 19 29 31 37 41 43 53 61 67 71 73 79 89 97 101 103 109 113 127 131 137 139 149 151 157 163 173 181 191 193 197 199 211 223 229 233 
Safe primes below 10,000,000: 30,657
Unsafe primes below 10,000,000: 633,922

zkl[edit]

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.

var [const] BI=Import("zklBigNum");  // libGMP
// saving 664,578 primes (vs generating them on the fly) seems a bit overkill

fcn safePrime(p){ ((p-1)/2).probablyPrime() } // p is a BigInt prime

fcn safetyList(sN,nsN){
   p,safe,notSafe := BI(2),List(),List();
   do{ 
      if(safePrime(p)) safe.append(p.toInt()) else notSafe.append(p.toInt()); 
      p.nextPrime();
   }while(safe.len()<sN or notSafe.len()<nsN);
   println("The first %d   safe primes are: %s".fmt(sN,safe[0,sN].concat(",")));
   println("The first %d unsafe primes are: %s".fmt(nsN,notSafe[0,nsN].concat(",")));
}(35,40);
Output:
The first 35   safe primes are: 5,7,11,23,47,59,83,107,167,179,227,263,347,359,383,467,479,503,563,587,719,839,863,887,983,1019,1187,1283,1307,1319,1367,1439,1487,1523,1619
The first 40 unsafe primes are: 2,3,13,17,19,29,31,37,41,43,53,61,67,71,73,79,89,97,101,103,109,113,127,131,137,139,149,151,157,163,173,181,191,193,197,199,211,223,229,233

safetyList could also be written as:

println("The first %d  safe primes are: %s".fmt(N:=35,
   Walker(BI(1).nextPrime)  // gyrate (vs Walker.filter) because p mutates
     .pump(N,String,safePrime,Void.Filter,String.fp1(","))));
println("The first %d unsafe primes are: %s".fmt(N=40,
   Walker(BI(1).nextPrime)	// or save as List
     .pump(N,List,safePrime,'==(False),Void.Filter,"toInt").concat(",")));

Time to count:

fcn safetyCount(N,s=0,ns=0,p=BI(2)){
   do{ 
      if(safePrime(p)) s+=1; else ns+=1;
      p.nextPrime()
   }while(p<N);
   println("The number of   safe primes below %10,d is %7,d".fmt(N,s));
   println("The number of unsafe primes below %10,d is %7,d".fmt(N,ns));
   return(s,ns,p);
}

s,ns,p := safetyCount(1_000_000);
println();
safetyCount(10_000_000,s,ns,p);
Output:
The number of   safe primes below  1,000,000 is   4,324
The number of unsafe primes below  1,000,000 is  74,174

The number of   safe primes below 10,000,000 is  30,657
The number of unsafe primes below 10,000,000 is 633,922