CalmoSoft primes: Difference between revisions
m
→{{header|Wren}}: Changed to Wren S/H
SqrtNegInf (talk | contribs) (Added Perl) |
m (→{{header|Wren}}: Changed to Wren S/H) |
||
| (3 intermediate revisions by 3 users not shown) | |||
Line 869:
Took 210 ms
</pre>
=={{header|Delphi}}==
{{works with|Delphi|6.0}}
{{libheader|SysUtils,StdCtrls}}
<syntaxhighlight lang="Delphi">
type TLongInfo = record
RangeStart,RangeStop: integer;
SeqStart,SeqStop: integer;
Count,Sum: integer;
end;
procedure CalmoSoftPrimes(Memo: TMemo);
{Find longest sequence of prime numbers that adds up to a prime}
var Sieve: TPrimeSieve;
var Best,Tmp: TLongInfo;
var I,Cnt: integer;
var S: string;
function GetLongest(N,Limit: integer): TLongInfo;
{Get longest sequence starting at N}
{Find longest sequence of primes whose sum is prime}
var Next,Sum,Cnt: integer;
begin
Result.Count:=1;
Result.SeqStart:=N;
Result.SeqStop:=N;
Result.Sum:=1;
Sum:=N; Next:=N;
Cnt:=1;
while true do
begin
Next:=Sieve.NextPrime(Next);
if Next>Limit then break;
Sum:=Sum+Next;
Inc(Cnt);
if IsPrime(Sum) then
begin
Result.SeqStop:=Next;
Result.Count:=Cnt;
Result.Sum:=Sum;
end;
end;
end;
function LongestRange(Start,Limit: integer): TLongInfo;
{Find longest sequence between Start and Limit}
{Start should be a prime number}
var I: integer;
begin
I:=Start;
Result.SeqStart:=0;
Result.SeqStop:=0;
Result.Count:=0;
while I<=Limit do
begin
Tmp:=GetLongest(I,Limit);
if Tmp.Count>Result.Count then Result:=Tmp;
I:=Sieve.NextPrime(I);
end;
Result.RangeStart:=Start;
Result.RangeStop:=Limit;
end;
procedure ShowSequenceHeader(Best: TLongInfo);
{Show summary of information}
begin
Memo.Lines.Add('Range: '+IntToStr(Best.RangeStart)+' '+IntToStr(Best.RangeStop));
Memo.Lines.Add('Longest Sequence: '+IntToStr(Best.Count));
Memo.Lines.Add('Sum: '+IntToStr(Best.Sum));
end;
procedure ShowSequence(Best: TLongInfo; Start,Limit: integer);
{Extract sequence info from best and display it}
var S: string;
var I,Cnt: integer;
begin
S:=''; Cnt:=0;
{if Start=0 display full range other wise}
{display from start to limit}
if Start=0 then I:=Best.SeqStart
else I:=Start;
while I<=Best.SeqStop do
begin
Inc(Cnt);
S:=S+Format('%5d',[I]);
if (Cnt mod 10)=0 then S:=S+CRLF;
if Cnt>=Limit then break;
I:=Sieve.NextPrime(I);
end;
Memo.Lines.Add(S);
end;
procedure ShowHeaderSequence(Best: TLongInfo);
{Show header and sequence}
begin
ShowSequenceHeader(Best);
ShowSequence(Best,0,high(integer));
end;
begin
Sieve:=TPrimeSieve.Create;
try
{Create enough primes to cover range}
Sieve.Intialize(1000);
{Find longest sequence in range}
Best:=LongestRange(2,100);
ShowHeaderSequence(Best);
finally Sieve.Free; end;
end;
</syntaxhighlight>
{{out}}
<pre>
Range: 2 100
Longest Sequence: 21
Sum: 953
7 11 13 17 19 23 29 31 37 41
43 47 53 59 61 67 71 73 79 83
89
Elapsed Time: 2.277 ms.
</pre>
=={{header|J}}==
It would be useful to find the length of the longest sequence of these primes where the sum is prime:
<syntaxhighlight lang=J> >./,(+/\\. 99#1)*1 p: +/\\. p:i.99
96</syntaxhighlight>
With this, we can check all sums of subsequences of 96 primes (from the first 99 primes) for primality:
<syntaxhighlight lang=J> 1 p: 96+/\p:i.99
1 0 0 0</syntaxhighlight>
In other words, the sum of these primes
<syntaxhighlight lang=J> p:i.8 12
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 337 347 349 353 359
367 373 379 383 389 397 401 409 419 421 431 433
439 443 449 457 461 463 467 479 487 491 499 503</syntaxhighlight>
is this prime:
<syntaxhighlight lang=J> +/p:i.96
22039</syntaxhighlight>
=={{header|Java}}==
Line 1,017 ⟶ 1,181:
Longest Calmo prime seq (length 3001117) of primes less than 50000000 totals 72618848632313
[7, 11, 13, 17, 19, 23, ... 49999699, 49999711, 49999739, 49999751, 49999753, 49999757]
</pre>
=={{header|Nim}}==
{{trans|Wren}}
With some modifications.
<syntaxhighlight lang="Nim">import std/[algorithm, math, strformat, strutils]
func initPrimes(lim: Natural): seq[int] =
## Build list of primes using a sieve of Erathostenes.
var composite = newSeq[bool]((lim + 1) shr 1)
composite[0] = true
for n in countup(3, int(sqrt(lim.toFloat)), 2):
if not composite[n shr 1]:
for k in countup(n * n, lim, 2 * n):
composite[k shr 1] = true
result.add 2
for n in countup(3, lim, 2):
if not composite[n shr 1]:
result.add n
func isPrime(n: Natural): bool =
## Return "true" is "n" is prime.
if n < 2: return false
if (n and 1) == 0: return n == 2
if n mod 3 == 0: return n == 3
var d = 5
var step = 2
while d * d <= n:
if n mod d == 0:
return false
inc d, step
step = 6 - step
return true
const Max = 50_000_000
let primes = initPrimes(Max)
proc calmoPrimes(limit: Positive): (int, seq[int], seq[int], seq[int]) =
## Find the longest sequence of CalmoSoft primes up to "limit".
let phigh = primes.upperBound(limit) - 1
var sum1 = sum(primes.toOpenArray(0, phigh))
var longest = 0
var sIndices, eIndices, sums: seq[int]
for i in 0..phigh:
if phigh - i + 1 < longest:
break
if i > 0:
dec sum1, primes[i - 1]
let isEven = i == 0
var sum2 = sum1
for j in countdown(phigh, i):
let temp = j - i + 1
if temp < longest:
break
if j < phigh:
dec sum2, primes[j + 1]
if ((temp and 1) == 0) != isEven:
continue
if sum2.isPrime:
if temp > longest:
longest = temp
sIndices = @[i]
eIndices = @[j]
sums = @[sum2]
else:
sIndices.add i
eIndices.add j
sums.add sum2
break
result = (longest, sIndices, eIndices, sums)
func plural(lg: int): (string, string) =
## Return the singular or plural form according to value of "lg".
result = if lg == 1: ("", "is") else: ("s", "are")
for limit in [100, 250, 5000, 10000, 500000, 50000000]:
let (longest, sIndices, eIndices, sums) = calmoPrimes(limit)
let (p1, p2) = plural(sums.len)
echo &"For primes up to {insertSep($limit)} the longest sequence{p1} of CalmoSoft primes"
echo &"having a length of {insertSep($longest)} {p2}:\n"
for i in 0..sIndices.high:
let cp = primes[sIndices[i]..eIndices[i]]
echo &"{cp[0..5].join(\" + \")} + ... + {cp[^6..^1].join(\" + \")} = {sums[i]}"
echo()
</syntaxhighlight>
{{out}}
<pre>For primes up to 100 the longest sequence of CalmoSoft primes
having a length of 21 is:
7 + 11 + 13 + 17 + 19 + 23 + ... + 67 + 71 + 73 + 79 + 83 + 89 = 953
For primes up to 250 the longest sequence of CalmoSoft primes
having a length of 49 is:
11 + 13 + 17 + 19 + 23 + 29 + ... + 223 + 227 + 229 + 233 + 239 + 241 = 5813
For primes up to 5_000 the longest sequence of CalmoSoft primes
having a length of 665 is:
7 + 11 + 13 + 17 + 19 + 23 + ... + 4957 + 4967 + 4969 + 4973 + 4987 + 4993 = 1543127
For primes up to 10_000 the longest sequences of CalmoSoft primes
having a length of 1_223 are:
3 + 5 + 7 + 11 + 13 + 17 + ... + 9883 + 9887 + 9901 + 9907 + 9923 + 9929 = 5686633
7 + 11 + 13 + 17 + 19 + 23 + ... + 9901 + 9907 + 9923 + 9929 + 9931 + 9941 = 5706497
For primes up to 500_000 the longest sequence of CalmoSoft primes
having a length of 41_530 is:
2 + 3 + 5 + 7 + 11 + 13 + ... + 499787 + 499801 + 499819 + 499853 + 499879 + 499883 = 9910236647
For primes up to 50_000_000 the longest sequence of CalmoSoft primes
having a length of 3_001_117 is:
7 + 11 + 13 + 17 + 19 + 23 + ... + 49999699 + 49999711 + 49999739 + 49999751 + 49999753 + 49999757 = 72618848632313
</pre>
Line 1,311 ⟶ 1,594:
{{libheader|Wren-fmt}}
This runs in about 3.5 seconds (cf. Julia 1.3 seconds) on my Core i7 machine. However, 2.6 seconds of that is needed to sieve for primes up to 50 million.
<syntaxhighlight lang="
import "./fmt"for Fmt
| |||