Rosetta Code

Safe primes and unsafe primes: Difference between revisions

Page Discussion

Safe primes and unsafe primes (view source)

Revision as of 23:46, 24 February 2024

18,126 bytes added ,  3 months ago
Added Easylang
(Add CLU)
(Added Easylang)
 
(9 intermediate revisions by 8 users not shown)
Line 31:
=={{header|ALGOL 68}}==
{{works with|ALGOL 68G|Any - tested with release 2.8.3.win32}}
<langsyntaxhighlight lang="algol68"># 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 #
Line 102:
print( ( newline ) );
print( ( "unsafe primes below 1,000,000: ", commatise( unsafe1 ), newline ) );
print( ( "unsafe primes below 10,000,000: ", commatise( unsafe10 ), newline ) )</langsyntaxhighlight>
{{out}}
<pre>
Line 116:
 
=={{header|AppleScript}}==
<langsyntaxhighlight lang="applescript">-- 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).
Line 240:
end doTask
 
return doTask()</langsyntaxhighlight>
 
{{output}}
<langsyntaxhighlight lang="applescript">"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.
Line 249:
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."</langsyntaxhighlight>
=={{header|Arturo}}==
<syntaxhighlight lang="arturo">primes: select 2..10000000 => prime?
 
safe?: function [n]->
prime? (n-1)/2
 
unsafe?: function [n]->
not? safe? n
 
printWithCommas: function [lst]->
join.with:", " to [:string] lst
 
print ["first 35 safe primes:"
primes | select.first:35 => safe?
| printWithCommas]
 
print ["safe primes below 1M:"
primes | select 'x -> x < 1000000
| enumerate => safe?]
 
print ["safe primes below 10M:"
primes | enumerate => safe?]
 
print ["first 40 unsafe primes:"
primes | select.first:40 => unsafe?
| printWithCommas]
 
print ["unsafe primes below 1M:"
primes | select 'x -> x < 1000000
| enumerate => unsafe?]
 
print ["unsafe primes below 10M:"
primes | enumerate => unsafe?]</syntaxhighlight>
 
{{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
safe primes below 1M: 4324
safe primes below 10M: 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 1M: 74174
unsafe primes below 10M: 633922</pre>
 
=={{header|AWK}}==
<syntaxhighlight lang="awk">
<lang AWK>
# syntax: GAWK -f SAFE_PRIMES_AND_UNSAFE_PRIMES.AWK
BEGIN {
Line 316 ⟶ 359:
return(1)
}
</syntaxhighlight>
</lang>
{{out}}
<pre>
Line 326 ⟶ 369:
Number below 10000000: 633922
</pre>
 
=={{header|BASIC256}}==
{{trans|FreeBASIC}}
<syntaxhighlight lang="basic256">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</syntaxhighlight>
 
 
=={{header|C}}==
<langsyntaxhighlight lang="c">#include <stdbool.h>
#include <stdio.h>
 
Line 421 ⟶ 535:
 
return 0;
}</langsyntaxhighlight>
{{out}}
<pre>First 35 safe primes:
Line 435 ⟶ 549:
=={{header|C sharp}}==
{{works with|C sharp|7}}
<langsyntaxhighlight lang="csharp">using static System.Console;
using System;
using System.Collections;
Line 476 ⟶ 590:
}
 
}</langsyntaxhighlight>
{{out}}
<pre>
Line 489 ⟶ 603:
 
=={{header|C++}}==
<langsyntaxhighlight lang="cpp">#include <algorithm>
#include <iostream>
#include <iterator>
Line 548 ⟶ 662:
unsafe_primes.print(std::cout, "unsafe");
return 0;
}</langsyntaxhighlight>
 
Contents of prime_sieve.hpp:
<langsyntaxhighlight lang="cpp">#ifndef PRIME_SIEVE_HPP
#define PRIME_SIEVE_HPP
 
Line 602 ⟶ 716:
}
 
#endif</langsyntaxhighlight>
 
{{out}}
Line 615 ⟶ 729:
 
=={{header|CLU}}==
<langsyntaxhighlight lang="clu">isqrt = proc (s: int) returns (int)
x0: int := s/2
if x0=0 then return(s) end
Line 693 ⟶ 807:
|| " " || ir.name || " primes < 1,000,000.\n")
end
end start_up</langsyntaxhighlight>
{{out}}
<pre>
Line 707 ⟶ 821:
 
=={{header|D}}==
<langsyntaxhighlight lang="d">import std.stdio;
 
immutable PRIMES = [
Line 800 ⟶ 914:
}
writefln("There are %6d unsafe primes below %9d", count, end);
}</langsyntaxhighlight>
{{out}}
<pre>First 35 safe primes:
Line 811 ⟶ 925:
There are 74174 unsafe primes below 1000000
There are 633922 unsafe primes below 10000000</pre>
 
=={{header|Delphi}}==
{{works with|Delphi|6.0}}
{{libheader|SysUtils,StdCtrls}}
 
 
<syntaxhighlight lang="Delphi">
{Uses seive object that creates an array of flags that tells whether a particular number is prime or not}
 
 
function GetSafeUnsafePrimes(MaxCount,MaxPrime: integer; ShowSafe, Display: boolean): string;
{MaxCount = Maximum number of Safe/Unsafe primes to find}
{MaxPrime = Maximum number of primes tested}
{ShowSafe = Controls whether we are looking for Save/Unsafe primes}
{Display = Controls whether the primes are displayed or just counted}
var I,Cnt: integer;
var Sieve: TPrimeSieve;
var IsSafe: boolean;
 
procedure CountAndDisplay;
begin
Inc(Cnt);
if Display then Result:=Result+Format('%7D',[I]);
If Display and ((Cnt mod 5)=0) then Result:=Result+CRLF;
end;
 
begin
{Create sieve and set sieve size}
Sieve:=TPrimeSieve.Create;
try
Sieve.Intialize(MaxPrime*2);
Cnt:=0;
Result:='';
I:=2;
while true do
begin
if I>=MaxPrime then break;
IsSafe:=(I>3) and Sieve[(I-1) div 2];
if IsSafe=ShowSafe then CountAndDisplay;
if Cnt>=MaxCount then break;
I:=Sieve.NextPrime(I);
end;
Result:=Result+'Count = '+FloatToStrF(Cnt,ffNumber,18,0);
finally Sieve.Free; end;
end;
 
 
procedure ShowSafeUnsafePrimes(Memo: TMemo);
var S: string;
begin
Memo.Lines.Add('The first 35 safe primes: ');
S:=GetSafeUnsafePrimes(35,10000000,True,True);
Memo.Lines.Add(S);
Memo.Lines.Add('Safe Primes Under 1,000,000: ');
S:=GetSafeUnsafePrimes(high(integer),1000000,True,False);
Memo.Lines.Add(S);
Memo.Lines.Add('Safe Primes Under 10,000,000: ');
S:=GetSafeUnsafePrimes(high(integer),10000000,True,False);
Memo.Lines.Add(S);
 
Memo.Lines.Add('The first 40 Unsafe primes: ');
S:=GetSafeUnsafePrimes(40,10000000,False,True);
Memo.Lines.Add(S);
Memo.Lines.Add('Unsafe Primes Under 1,000,000: ');
S:=GetSafeUnsafePrimes(high(integer),1000000,False,False);
Memo.Lines.Add(S);
Memo.Lines.Add('Unsafe Primes Under 10,000,000: ');
S:=GetSafeUnsafePrimes(high(integer),10000000,False,False);
Memo.Lines.Add(S);
end;
 
 
</syntaxhighlight>
{{out}}
<pre>
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 = 35
Safe Primes Under 1,000,000:
Count = 4,324
Safe Primes Under 10,000,000:
Count = 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 = 40
Unsafe Primes Under 1,000,000:
Count = 74,174
Unsafe Primes Under 10,000,000:
Count = 633,922
Elapsed Time: 816.075 ms.
</pre>
 
=={{header|EasyLang}}==
{{trans|C}}
<syntaxhighlight>
fastfunc isprim num .
if num < 2
return 0
.
if num mod 2 = 0
if num = 2
return 1
.
return 0
.
i = 3
while i <= sqrt num
if num mod i = 0
return 0
.
i += 2
.
return 1
.
print "First 35 safe primes:"
for i = 2 to 999999
if isprim i = 1 and isprim ((i - 1) / 2) = 1
if count < 35
write i & " "
.
count += 1
.
.
print ""
print "There are " & count & " safe primes below 1000000"
for i = i to 9999999
if isprim i = 1 and isprim ((i - 1) / 2) = 1
count += 1
.
.
print "There are " & count & " safe primes below 10000000"
print ""
count = 0
print "First 40 unsafe primes:"
for i = 2 to 999999
if isprim i = 1 and isprim ((i - 1) / 2) = 0
if count < 40
write i & " "
.
count += 1
.
.
print ""
print "There are " & count & " unsafe primes below 1000000"
for i = i to 9999999
if isprim i = 1 and isprim ((i - 1) / 2) = 0
count += 1
.
.
print "There are " & count & " unsafe primes below 10000000"
</syntaxhighlight>
 
{{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
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
</pre>
 
=={{header|F_Sharp|F#}}==
This task uses [http://www.rosettacode.org/wiki/Extensible_prime_generator#The_function Extensible Prime Generator (F#)]<langsyntaxhighlight lang="fsharp">
pCache |> Seq.filter(fun n->isPrime((n-1)/2)) |> Seq.take 35 |> Seq.iter (printf "%d ")
</syntaxhighlight>
</lang>
{{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>
<langsyntaxhighlight lang="fsharp">
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)
</syntaxhighlight>
</lang>
{{out}}
<pre>
There are 4324 safe primes less than 10000000
</pre>
<langsyntaxhighlight lang="fsharp">
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)
</syntaxhighlight>
</lang>
{{out}}
<pre>
There are 30657 safe primes less than 10000000
</pre>
<langsyntaxhighlight lang="fsharp">
pCache |> Seq.filter(fun n->not (isPrime((n-1)/2))) |> Seq.take 40 |> Seq.iter (printf "%d ")
</syntaxhighlight>
</lang>
{{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>
<langsyntaxhighlight lang="fsharp">
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);;
</syntaxhighlight>
</lang>
{{out}}
<pre>
There are 74174 unsafe primes less than 1000000
</pre>
<langsyntaxhighlight lang="fsharp">
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);;
</syntaxhighlight>
</lang>
{{out}}
<pre>
Line 858 ⟶ 1,149:
=={{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.
<langsyntaxhighlight lang="factor">USING: fry interpolate kernel literals math math.primes
sequences tools.memory.private ;
IN: rosetta-code.safe-primes
Line 886 ⟶ 1,177:
Unsafe prime count below 1,000,000: ${1}
Unsafe prime count below 10,000,000: ${}
I]</langsyntaxhighlight>
{{out}}
<pre>
Line 901 ⟶ 1,192:
 
=={{header|FreeBASIC}}==
<langsyntaxhighlight lang="freebasic">' version 19-01-2019
' compile with: fbc -s console
 
Line 975 ⟶ 1,266:
Print : Print "hit any key to end program"
Sleep
End</langsyntaxhighlight>
{{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
Line 987 ⟶ 1,278:
 
=={{header|Frink}}==
<langsyntaxhighlight lang="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] }]
Line 998 ⟶ 1,289:
println["Unsafe primes below 1,000,000: " + length[unsafePrimes[1_000_000]]]
println["Unsafe primes below 10,000,000: " + length[unsafePrimes[10_000_000]]]
</syntaxhighlight>
</lang>
 
{{out}}
Line 1,011 ⟶ 1,302:
 
=={{header|Go}}==
<langsyntaxhighlight lang="go">package main
 
import "fmt"
Line 1,112 ⟶ 1,403:
}
fmt.Println("The number of unsafe primes below 10,000,000 is", commatize(count), "\n")
}</langsyntaxhighlight>
 
{{out}}
Line 1,132 ⟶ 1,423:
=={{header|Haskell}}==
Uses Numbers.Prime library: http://hackage.haskell.org/package/primes-0.2.1.0/docs/Data-Numbers-Primes.html
<langsyntaxhighlight lang="haskell">
import Text.Printf (printf)
import Data.Numbers.Primes (isPrime, primes)
Line 1,147 ⟶ 1,438:
where safe = filter (\n -> isPrime ((n-1) `div` 2)) primes
unsafe = filter (\n -> not (isPrime((n-1) `div` 2))) primes
</syntaxhighlight>
</lang>
{{out}}
<pre>
Line 1,216 ⟶ 1,507:
</pre>
Essentially we have
<syntaxhighlight lang="j">
<lang J>
primeQ =: 1&p:
safeQ =: primeQ@:-:@:<:
Line 1,224 ⟶ 1,515:
SAFE =: safeQ Filter PRIMES
UNSAFE =: PRIMES -. SAFE
</syntaxhighlight>
</lang>
The rest of the display is mere window dressing.
 
=={{header|Java}}==
<langsyntaxhighlight lang="java">public class SafePrimes {
public static void main(String... args) {
// Use Sieve of Eratosthenes to find primes
Line 1,293 ⟶ 1,584:
return;
}
}</langsyntaxhighlight>
{{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
Line 1,305 ⟶ 1,596:
{{works with|jq}}
To save memory, we use a memory-less `is_prime` algorithm, but with a long preamble.
<syntaxhighlight lang="jq">
<lang jq>
def is_prime:
. as $n
Line 1,366 ⟶ 1,657:
;
 
task</langsyntaxhighlight>
{{out}}
<pre>
Line 1,387 ⟶ 1,678:
 
=={{header|Julia}}==
<langsyntaxhighlight lang="julia">using Primes, Formatting
 
function parseprimelist()
Line 1,409 ⟶ 1,700:
 
parseprimelist()
</langsyntaxhighlight> {{output}} <pre>
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.
Line 1,420 ⟶ 1,711:
=={{header|Kotlin}}==
{{trans|Go}}
<langsyntaxhighlight lang="scala">// Version 1.2.70
 
fun sieve(limit: Int): BooleanArray {
Line 1,487 ⟶ 1,778:
}
System.out.printf("The number of unsafe primes below 10,000,000 is %,d\n\n", count)
}</langsyntaxhighlight>
 
{{output}}
Line 1,507 ⟶ 1,798:
 
=={{header|Ksh}}==
<langsyntaxhighlight lang="ksh">
#!/bin/ksh
 
Line 1,569 ⟶ 1,860:
print "There are ${unsacnt1M} under 1,000,000"
print "There are ${unsacnt} under 10,000,000"
</syntaxhighlight>
</lang>
{{out}}<pre>
Safe primes:
Line 1,581 ⟶ 1,872:
 
=={{header|Lua}}==
<langsyntaxhighlight lang="lua">-- 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
Line 1,600 ⟶ 1,891:
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))</langsyntaxhighlight>
{{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
Line 1,610 ⟶ 1,901:
 
=={{header|Maple}}==
<langsyntaxhighlight Maplelang="maple">showSafePrimes := proc(n::posint)
local prime_list, k;
prime_list := [5];
Line 1,650 ⟶ 1,941:
countSafePrimes(10000000);
countUnsafePrimes(1000000);
countUnsafePrimes(10000000);</langsyntaxhighlight>
{{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]
Line 1,660 ⟶ 1,951:
 
=={{header|Mathematica}}/{{header|Wolfram Language}}==
<langsyntaxhighlight Mathematicalang="mathematica">ClearAll[SafePrimeQ, UnsafePrimeQ]
SafePrimeQ[n_Integer] := PrimeQ[n] \[And] PrimeQ[(n - 1)/2]
UnsafePrimeQ[n_Integer] := PrimeQ[n] \[And] ! PrimeQ[(n - 1)/2]
Line 1,686 ⟶ 1,977:
 
Count[Range[PrimePi[10^6]], _?(Prime /* UnsafePrimeQ)]
Count[Range[PrimePi[10^7]], _?(Prime /* UnsafePrimeQ)]</langsyntaxhighlight>
{{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}
Line 1,696 ⟶ 1,987:
 
=={{header|Nim}}==
<langsyntaxhighlight Nimlang="nim">import sequtils, strutils
 
const N = 10_000_000
Line 1,741 ⟶ 2,032:
($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)</langsyntaxhighlight>
 
{{out}}
Line 1,757 ⟶ 2,048:
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.
<langsyntaxhighlight lang="pascal">program Sophie;
{ Find and count Sophie Germain primes }
{ uses unit mp_prime out of mparith of Wolfgang Ehrhardt
Line 1,865 ⟶ 2,156:
T1 :=gettickcount64;
writeln('runtime ',T1-T0,' ms');
end.</langsyntaxhighlight>
{{output}}
<pre>First 35 safe primes
Line 1,882 ⟶ 2,173:
The module <code>ntheory</code> does fast prime generation and testing.
{{libheader|ntheory}}
<langsyntaxhighlight lang="perl">use ntheory qw(forprimes is_prime);
 
my $upto = 1e7;
Line 1,905 ⟶ 2,196:
$s =~ s/,(-?)$/$1/;
$s = reverse $s;
}</langsyntaxhighlight>
{{out}}
<pre>The first 35 safe primes are:
Line 1,917 ⟶ 2,208:
 
=={{header|Phix}}==
<!--<syntaxhighlight lang="phix">(phixonline)-->
<lang Phix>sequence safe = {}, unsafe = {}
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span>
function filter_range(integer lo, hi)
<span style="color: #004080;">sequence</span> <span style="color: #000000;">safe</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{},</span> <span style="color: #000000;">unsafe</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{}</span>
while true do
<span style="color: #008080;">function</span> <span style="color: #000000;">filter_range</span><span style="color: #0000FF;">(</span><span style="color: #004080;">integer</span> <span style="color: #000000;">lo</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">hi</span><span style="color: #0000FF;">)</span>
integer p = get_prime(lo)
<span style="color: #008080;">while</span> <span style="color: #004600;">true</span> <span style="color: #008080;">do</span>
if p>hi then return lo end if
<span style="color: #004080;">integer</span> <span style="color: #000000;">p</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">get_prime</span><span style="color: #0000FF;">(</span><span style="color: #000000;">lo</span><span style="color: #0000FF;">)</span>
if p>2 and is_prime((p-1)/2) then
<span style="color: #008080;">if</span> <span style="color: #000000;">p</span><span style="color: #0000FF;">></span><span style="color: #000000;">hi</span> <span style="color: #008080;">then</span> <span style="color: #008080;">return</span> <span style="color: #000000;">lo</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
safe &= p
<span style="color: #008080;">if</span> <span style="color: #000000;">p</span><span style="color: #0000FF;">></span><span style="color: #000000;">2</span> <span style="color: #008080;">and</span> <span style="color: #7060A8;">is_prime</span><span style="color: #0000FF;">((</span><span style="color: #000000;">p</span><span style="color: #0000FF;">-</span><span style="color: #000000;">1</span><span style="color: #0000FF;">)/</span><span style="color: #000000;">2</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">then</span>
else
<span style="color: #000000;">safe</span> <span style="color: #0000FF;">&=</span> <span style="color: #000000;">p</span>
unsafe &= p
<span style="color: #008080;">else</span>
end if
<span style="color: #000000;">unsafe</span> <span style="color: #0000FF;">&=</span> <span style="color: #000000;">p</span>
lo += 1
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
end while
<span style="color: #000000;">lo</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">1</span>
end function
<span style="color: #008080;">end</span> <span style="color: #008080;">while</span>
integer lo = filter_range(1,1_000_000),
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
ls = length(safe),
<span style="color: #004080;">integer</span> <span style="color: #000000;">lo</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">filter_range</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">1_000_000</span><span style="color: #0000FF;">),</span>
lu = length(unsafe)
<span style="color: #000000;">ls</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">safe</span><span style="color: #0000FF;">),</span>
{} = filter_range(lo,10_000_000)
<span style="color: #000000;">lu</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">unsafe</span><span style="color: #0000FF;">)</span>
printf(1,"The first 35 safe primes: %v\n",{safe[1..35]})
<span style="color: #0000FF;">{}</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">filter_range</span><span style="color: #0000FF;">(</span><span style="color: #000000;">lo</span><span style="color: #0000FF;">,</span><span style="color: #000000;">10_000_000</span><span style="color: #0000FF;">)</span>
printf(1,"Count of safe primes below 1,000,000: %,d\n",ls)
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"The first 35 safe primes: %v\n"</span><span style="color: #0000FF;">,{</span><span style="color: #000000;">safe</span><span style="color: #0000FF;">[</span><span style="color: #000000;">1</span><span style="color: #0000FF;">..</span><span style="color: #000000;">35</span><span style="color: #0000FF;">]})</span>
printf(1,"Count of safe primes below 10,000,000: %,d\n",length(safe))
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"Count of safe primes below 1,000,000: %,d\n"</span><span style="color: #0000FF;">,</span><span style="color: #000000;">ls</span><span style="color: #0000FF;">)</span>
printf(1,"The first 40 unsafe primes: %v\n",{unsafe[1..40]})
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"Count of safe primes below 10,000,000: %,d\n"</span><span style="color: #0000FF;">,</span><span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">safe</span><span style="color: #0000FF;">))</span>
printf(1,"Count of unsafe primes below 1,000,000: %,d\n",lu)
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"The first 40 unsafe primes: %v\n"</span><span style="color: #0000FF;">,{</span><span style="color: #000000;">unsafe</span><span style="color: #0000FF;">[</span><span style="color: #000000;">1</span><span style="color: #0000FF;">..</span><span style="color: #000000;">40</span><span style="color: #0000FF;">]})</span>
printf(1,"Count of unsafe primes below 10,000,000: %,d\n",length(unsafe))</lang>
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"Count of unsafe primes below 1,000,000: %,d\n"</span><span style="color: #0000FF;">,</span><span style="color: #000000;">lu</span><span style="color: #0000FF;">)</span>
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"Count of unsafe primes below 10,000,000: %,d\n"</span><span style="color: #0000FF;">,</span><span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">unsafe</span><span style="color: #0000FF;">))</span>
<!--</syntaxhighlight>-->
{{out}}
<pre style="font-size: 11px">
Line 1,951 ⟶ 2,245:
 
=={{header|PureBasic}}==
<langsyntaxhighlight PureBasiclang="purebasic">#MAX=10000000
Global Dim P.b(#MAX) : FillMemory(@P(),#MAX,1,#PB_Byte)
Global NewList Primes.i()
Line 1,981 ⟶ 2,275:
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()</langsyntaxhighlight>
{{out}}
<pre>First 35 safe primes:
Line 1,995 ⟶ 2,289:
 
=={{header|Python}}==
<syntaxhighlight lang="python">
<lang Python>
primes =[]
sp =[]
Line 2,021 ⟶ 2,315:
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')
</syntaxhighlight>
</lang>
{{out}}
<pre style="font-size: 11px">
Line 2,039 ⟶ 2,333:
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.
 
<syntaxhighlight lang="raku" perl6line>sub comma { $^i.flip.comb(3).join(',').flip }
 
use Math::Primesieve;
Line 2,060 ⟶ 2,354:
 
say '';
}</langsyntaxhighlight>
{{out}}
<pre>The first 35 safe primes are:
Line 2,073 ⟶ 2,367:
 
=={{header|REXX}}==
<langsyntaxhighlight lang="rexx">/*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.*/
Line 2,122 ⟶ 2,416:
else return add() /*is " " " */
else if @.? == '' then return add() /*is an unsafe prime.*/
else return 0 /*not " " " */</langsyntaxhighlight>
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.
Line 2,169 ⟶ 2,463:
 
=={{header|Ring}}==
<langsyntaxhighlight lang="ring">
load "stdlib.ring"
 
Line 2,254 ⟶ 2,548:
 
see "done..." + nl
</syntaxhighlight>
</lang>
Output:
<pre>
Line 2,269 ⟶ 2,563:
</pre>
 
 
 
{{works with|HP|49g}}
≪
1 - 2 /
'''IFERR''' ISPRIME? '''THEN''' DROP 0 '''END'''
≫ '<span style="color:blue">SAFE?</span>' STO
≪ → function count
≪ { } 2
'''WHILE''' OVER SIZE count < '''REPEAT '''
'''IF''' DUP function EVAL '''THEN''' SWAP OVER + SWAP '''END'''
NEXTPRIME
'''END'''
DROP
≫ ≫ '<span style="color:blue">FIRSTSEQ</span>' STO
≪ → function max
≪ 0 2
'''WHILE''' DUP max < '''REPEAT '''
'''IF''' DUP function EVAL '''THEN''' SWAP 1 + SWAP '''END'''
NEXTPRIME
'''END'''
DROP
≫ ≫ '<span style="color:blue">CNTSEQ</span>' STO
 
≪ <span style="color:blue">SAFE?</span> ≫ 35 <span style="color:blue">FIRSTSEQ</span>
≪ <span style="color:blue">SAFE?</span> ≫ 10000 <span style="color:blue">CNTSEQ</span>
≪ <span style="color:blue">SAFE?</span> NOT ≫ 40 <span style="color:blue">FIRSTSEQ</span>
≪ <span style="color:blue">SAFE?</span> NOT ≫ 10000 <span style="color:blue">CNTSEQ</span>
Counting safe numbers up to one million would take an hour, without really creating any opportunity to improve the algorithm or the code.
{{out}
<pre>
4: {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}
3: 115
2: {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}
1: 1114
</pre>
 
 
=={{header|Ruby}}==
<langsyntaxhighlight lang="ruby">require "prime"
class Integer
def safe_prime? #assumes prime
Line 2,291 ⟶ 2,623:
p Prime.each.lazy.reject(&:safe_prime?).take(40).to_a
puts format_parts(10_000_000)
</syntaxhighlight>
</lang>
{{out}}
<pre>
Line 2,305 ⟶ 2,637:
 
=={{header|Rust}}==
<langsyntaxhighlight lang="rust">fn is_prime(n: i32) -> bool {
for i in 2..n {
if i * i > n {
Line 2,386 ⟶ 2,718:
println!("safe primes below 10,000,000: {}", safe);
println!("unsafe primes below 10,000,000: {}", unsf);
}</langsyntaxhighlight>
<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
Line 2,397 ⟶ 2,729:
 
=={{header|Shale}}==
<langsyntaxhighlight Shalelang="shale">#!/usr/local/bin/shale
 
// Safe and unsafe primes.
Line 2,485 ⟶ 2,817:
init()
go()
</syntaxhighlight>
</lang>
 
{{out}}
Line 2,498 ⟶ 2,830:
 
=={{header|Sidef}}==
<langsyntaxhighlight lang="ruby">func is_safeprime(p) {
is_prime(p) && is_prime((p-1)/2)
}
Line 2,524 ⟶ 2,856:
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"</langsyntaxhighlight>
{{out}}
<pre>
Line 2,541 ⟶ 2,873:
 
=={{header|Simula}}==
<langsyntaxhighlight lang="simula">
BEGIN
 
Line 2,683 ⟶ 3,015:
 
END
</syntaxhighlight>
</lang>
{{out}}
<pre>
Line 2,705 ⟶ 3,037:
=={{header|Smalltalk}}==
{{works with|Smalltalk/X}}
<langsyntaxhighlight lang="smalltalk">[
| isSafePrime printFirstNElements |
Line 2,746 ⟶ 3,078:
Transcript showCR:nUnsaveBelow10M printStringWithThousandsSeparator.
]
] benchmark:'runtime: safe primes'</langsyntaxhighlight>
{{out}}
<pre>
Line 2,768 ⟶ 3,100:
 
=={{header|Swift}}==
<langsyntaxhighlight lang="swift">import Foundation
 
class PrimeSieve {
Line 2,854 ⟶ 3,186:
 
safePrimes.printInfo(name: "safe")
unsafePrimes.printInfo(name: "unsafe")</langsyntaxhighlight>
 
{{out}}
Line 2,868 ⟶ 3,200:
=={{header|Visual Basic .NET}}==
{{trans|C#}}Dependent on using .NET Core 2.1 or 2.0, or .NET Framework 4.7.2
<langsyntaxhighlight lang="vbnet">Imports System.Console
 
Namespace safety
Line 2,901 ⟶ 3,233:
End Function
End Module
End Namespace</langsyntaxhighlight>
If not using the latest version of the '''System.Linq''' namespace, you can implement the ''Enumerable.ToHashSet()'' method by adding <langsyntaxhighlight lang="vbnet">Imports System.Runtime.CompilerServices</langsyntaxhighlight> to the top and this module inside the '''safety''' namespace:<langsyntaxhighlight lang="vbnet"> Module Extensions
<Extension()>
Function ToHashSet(Of T)(ByVal src As IEnumerable(Of T), ByVal Optional _
Line 2,908 ⟶ 3,240:
Return New HashSet(Of T)(src, IECmp)
End Function
End Module</langsyntaxhighlight>
{{out}}
<pre>The first 35 safe primes are:
Line 2,921 ⟶ 3,253:
{{libheader|Wren-math}}
{{libheader|Wren-fmt}}
<langsyntaxhighlight ecmascriptlang="wren">import "./math" for Int
import "./fmt" for Fmt
 
var c = Int.primeSieve(1e7, false) // need primes up to 10 million here
Line 2,974 ⟶ 3,306:
i = i + 2
}
Fmt.print("The number of unsafe primes below 10,000,000 is $,d.\n", count)</langsyntaxhighlight>
 
{{out}}
Line 2,991 ⟶ 3,323:
 
The number of unsafe primes below 10,000,000 is 633,922.
</pre>
 
=={{header|XPL0}}==
<syntaxhighlight lang="xpl0">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);
]</syntaxhighlight>
 
{{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
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
</pre>
 
Line 2,998 ⟶ 3,398:
 
[[Extensible prime generator#zkl]] could be used instead.
<langsyntaxhighlight lang="zkl">var [const] BI=Import("zklBigNum"); // libGMP
// saving 664,578 primes (vs generating them on the fly) seems a bit overkill
 
Line 3,011 ⟶ 3,411:
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);</langsyntaxhighlight>
{{out}}
<pre>
Line 3,018 ⟶ 3,418:
</pre>
safetyList could also be written as:
<langsyntaxhighlight lang="zkl">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(",")));</langsyntaxhighlight>
Time to count:
<langsyntaxhighlight lang="zkl">fcn safetyCount(N,s=0,ns=0,p=BI(2)){
do{
if(safePrime(p)) s+=1; else ns+=1;
Line 3,037 ⟶ 3,437:
s,ns,p := safetyCount(1_000_000);
println();
safetyCount(10_000_000,s,ns,p);</langsyntaxhighlight>
{{out}}
<pre>
Chkas
2,033

edits

Retrieved from "https://rosettacode.org/wiki/Special:MobileDiff/285566...353636"