Safe primes and unsafe primes: Difference between revisions

=={{header|ALGOL 68}}==

{{works with|ALGOL 68G|Any - tested with release 2.8.3.win32}}

# safe primes are primes p such that ( p - 1 ) / 2 is also prime #

# unsafe primes are primes that are not safe #

print( ( newline ) );

print( ( "unsafe primes below 1,000,000: ", commatise( unsafe1 ), newline ) );

{{out}}

<pre>

unsafe primes below 10,000,000: 633,922

</pre>

 

=={{header|C}}==

#include <stdio.h>

 

 

return 0;

{{out}}

<pre>First 35 safe primes:

=={{header|C sharp}}==

{{works with|C sharp|7}}

using System;

using System.Collections;

}

 

{{out}}

<pre>

 

=={{header|C++}}==

#include <locale>

#include "prime_sieve.hpp"

 

 

// 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

for (int p = 2; p < limit2; ++p) {

}

}

return 0;

 

Contents of prime_sieve.hpp:

#define PRIME_SIEVE_HPP

 

}

 

 

{{out}}

<pre>

Number of safe primes below 1,000,000: 4,324

Number of safe primes below 10,000,000: 30,657

Number of unsafe primes below 1,000,000: 74,174

Number of unsafe primes below 10,000,000: 633,922

</pre>

 

=={{header|D}}==

 

immutable PRIMES = [

}

writefln("There are %6d unsafe primes below %9d", count, end);

{{out}}

<pre>First 35 safe primes:

There are 74174 unsafe primes below 1000000

There are 633922 unsafe primes below 10000000</pre>

 

=={{header|F_Sharp|F#}}==

pCache |> Seq.filter(fun n->isPrime((n-1)/2)) |> Seq.take 35 |> Seq.iter (printf "%d ")

{{out}}

<pre>

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

</pre>

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)

{{out}}

<pre>

There are 4324 safe primes less than 10000000

</pre>

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)

{{out}}

<pre>

There are 30657 safe primes less than 10000000

</pre>

pCache |> Seq.filter(fun n->not (isPrime((n-1)/2))) |> Seq.take 40 |> Seq.iter (printf "%d ")

{{out}}

<pre>

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

</pre>

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

{{out}}

<pre>

There are 74174 unsafe primes less than 1000000

</pre>

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

{{out}}

<pre>

=={{header|Factor}}==

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.

sequences tools.memory.private ;

IN: rosetta-code.safe-primes

Unsafe prime count below 1,000,000: ${1}

Unsafe prime count below 10,000,000: ${}

{{out}}

<pre>

 

=={{header|FreeBASIC}}==

' compile with: fbc -s console

 

Print : Print "hit any key to end program"

Sleep

{{out}}

<pre>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

 

=={{header|Frink}}==

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["Unsafe primes below 1,000,000: " + length[unsafePrimes[1_000_000]]]

println["Unsafe primes below 10,000,000: " + length[unsafePrimes[10_000_000]]]

 

{{out}}

 

=={{header|Go}}==

 

import "fmt"

}

fmt.Println("The number of unsafe primes below 10,000,000 is", commatize(count), "\n")

 

{{out}}

=={{header|Haskell}}==

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)

where safe = filter (\n -> isPrime ((n-1) `div` 2)) primes

unsafe = filter (\n -> not (isPrime((n-1) `div` 2))) primes

{{out}}

<pre>

</pre>

Essentially we have

primeQ =: 1&p:

safeQ =: primeQ@:-:@:<:

SAFE =: safeQ Filter PRIMES

UNSAFE =: PRIMES -. SAFE

The rest of the display is mere window dressing.

 

=={{header|Java}}==

public static void main(String... args) {

// Use Sieve of Eratosthenes to find primes

return;

}

{{out}}

<pre>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 unsafe primes below 1,000,000: 74174

Number of unsafe primes below 10,000,000: 633922</pre>

 

=={{header|Julia}}==

 

function parseprimelist()

 

parseprimelist()

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.

=={{header|Kotlin}}==

{{trans|Go}}

 

fun sieve(limit: Int): BooleanArray {

}

System.out.printf("The number of unsafe primes below 10,000,000 is %,d\n\n", count)

 

{{output}}

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

</pre>

 

=={{header|Lua}}==

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

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)))

{{out}}

<pre>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

 

=={{header|Maple}}==

local prime_list, k;

prime_list := [5];

countSafePrimes(10000000);

countUnsafePrimes(1000000);

{{out}}

<pre>[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]

74174

633922</pre>

 

=={{header|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.

{ Find and count Sophie Germain primes }

{ uses unit mp_prime out of mparith of Wolfgang Ehrhardt

T1 :=gettickcount64;

writeln('runtime ',T1-T0,' ms');

{{output}}

<pre>First 35 safe primes

The module <code>ntheory</code> does fast prime generation and testing.

{{libheader|ntheory}}

 

my $upto = 1e7;

$s =~ s/,(-?)$/$1/;

$s = reverse $s;

{{out}}

<pre>The first 35 safe primes are:

 

=={{header|Phix}}==

{{out}}

<pre style="font-size: 11px">

Count of unsafe primes below 1,000,000: 74,174

Count of unsafe primes below 10,000,000: 633,922

</pre>

 

=={{header|Python}}==

primes =[]

sp =[]

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')

{{out}}

<pre style="font-size: 11px">

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.

 

 

use Math::Primesieve;

 

say '';

{{out}}

<pre>The first 35 safe primes are:

 

=={{header|REXX}}==

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.*/

else return add() /*is " " " */

else if @.? == '' then return add() /*is an unsafe prime.*/

This REXX program makes use of &nbsp; '''LINESIZE''' &nbsp; REXX program (or BIF) which is used to determine

the screen width (or linesize) of the terminal (console). &nbsp; Some REXXes don't have this BIF.

 

=={{header|Ring}}==

load "stdlib.ring"

 

 

see "done..." + nl

Output:

<pre>

</pre>

 

 

 

=={{header|Ruby}}==

class Integer

def safe_prime? #assumes prime

p Prime.each.lazy.reject(&:safe_prime?).take(40).to_a

puts format_parts(10_000_000)

{{out}}

<pre>

There are 30657 safes and 633922 unsafes below 10000000.

 

</pre>

 

=={{header|Sidef}}==

is_prime(p) && is_prime((p-1)/2)

}

say ''

say "There are #{safeprime_count(1, 1e7)} safe-primes bellow 10^7"

{{out}}

<pre>

 

=={{header|Simula}}==

BEGIN

 

 

END

{{out}}

<pre>

=={{header|Smalltalk}}==

{{works with|Smalltalk/X}}

| isSafePrime printFirstNElements |

Transcript showCR:nUnsaveBelow10M printStringWithThousandsSeparator.

]

{{out}}

<pre>

But, who cares, these days ;-)

<br>3) time is on a 2012 MacBook 2.5Ghz i5; interpreted not jitted. Compiled/jitted time is 738ms.

 

=={{header|Visual Basic .NET}}==

{{trans|C#}}Dependent on using .NET Core 2.1 or 2.0, or .NET Framework 4.7.2

 

Namespace safety

End Function

End Module

<Extension()>

Function ToHashSet(Of T)(ByVal src As IEnumerable(Of T), ByVal Optional _

Return New HashSet(Of T)(src, IECmp)

End Function

{{out}}

<pre>The first 35 safe primes are:

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.

</pre>

 

 

[[Extensible prime generator#zkl]] could be used instead.

// saving 664,578 primes (vs generating them on the fly) seems a bit overkill

 

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(",")));

{{out}}

<pre>

</pre>

safetyList could also be written as:

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

Time to count:

do{

if(safePrime(p)) s+=1; else ns+=1;

s,ns,p := safetyCount(1_000_000);

println();

{{out}}

<pre>