CalmoSoft primes: Difference between revisions
Content added Content deleted
(→{{header|ALGOL 68}}: comments) |
(Added XPL0 example.) |
||
Line 308: | Line 308: | ||
7 + 11 + 13 + 17 + 19 + 23 + 29 + 31 + 37 + 41 + 43 + 47 + 53 + 59 + 61 + 67 + 71 + 73 + 79 + 83 + 89 = 953 which is prime |
7 + 11 + 13 + 17 + 19 + 23 + 29 + 31 + 37 + 41 + 43 + 47 + 53 + 59 + 61 + 67 + 71 + 73 + 79 + 83 + 89 = 953 which is prime |
||
</pre> |
|||
=={{header|XPL0}}== |
|||
<syntaxhighlight lang "XPL0">include xpllib; \for IsPrime and Print |
|||
int Primes(100), PrimeSums(100); |
|||
int I, N, Size, Head, Tail, Longest, Sum, SaveHead, SaveTail; |
|||
[I:= 0; \make table of primes |
|||
for N:= 2 to 100-1 do |
|||
if IsPrime(N) then |
|||
[Primes(I):= N; I:= I+1]; |
|||
Size:= I; \make table of sums |
|||
PrimeSums(0):= Primes(0); |
|||
for I:= 1 to Size-1 do |
|||
PrimeSums(I):= PrimeSums(I-1) + Primes(I); |
|||
Longest:= 0; \find longest sequence |
|||
for Head:= Size-1 downto 0 do |
|||
[Sum:= PrimeSums(Head); |
|||
for Tail:= 0 to Head do |
|||
[if Head-Tail > Longest then |
|||
[if IsPrime(Sum) then |
|||
[Longest:= Head-Tail; |
|||
SaveHead:= Head; |
|||
SaveTail:= Tail; |
|||
]; |
|||
]; |
|||
Sum:= Sum - Primes(Tail); |
|||
]; |
|||
]; |
|||
Print( "The longest sequence of CalmoSoft primes < 100 is %d:\n", Longest+1); |
|||
Sum:= 0; |
|||
for I:= SaveTail to SaveHead do |
|||
[Sum:= Sum + Primes(I); |
|||
IntOut(0, Primes(I)); |
|||
if I # SaveHead then ChOut(0, ^+); |
|||
]; |
|||
Print(" = %d\n", Sum); |
|||
]</syntaxhighlight> |
|||
{{out}} |
|||
<pre> |
|||
The longest sequence of CalmoSoft primes < 100 is 21: |
|||
7+11+13+17+19+23+29+31+37+41+43+47+53+59+61+67+71+73+79+83+89 = 953 |
|||
</pre> |
</pre> |
Revision as of 16:50, 7 April 2023
CalmoSoft primes is a draft programming task. It is not yet considered ready to be promoted as a complete task, for reasons that should be found in its talk page.
- Definition
Let p(1), p(2), p(3), ... , p(n) be consecutive prime numbers, where p(n) < 100. If the sum of any consecutive sub-sequence of these numbers is a prime number, then the numbers in such a sub-sequence are called CalmoSoft primes.
- Task
Find and show here the longest sequence of CalmoSoft primes.
ALGOL 68
If there are multiple sequences with the maximum length, this will only show the first.
BEGIN # find the longest sequence of primes < 100 that sums to a prime #
# called Calmosoft primes #
[]INT prime = ( 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
); # primes up to 100 #
# returns TRUE if n is prime, FALSE otherwise - uses trial division #
PROC is prime = ( INT n )BOOL:
IF n < 3 THEN n = 2
ELIF n MOD 3 = 0 THEN n = 3
ELIF NOT ODD n THEN FALSE
ELSE
BOOL is a prime := TRUE;
FOR f FROM 5 BY 2 WHILE f * f <= n AND ( is a prime := n MOD f /= 0 )
DO SKIP OD;
is a prime
FI # is prime # ;
# calculate the sum of all the primes #
INT seq sum := 0; FOR i FROM LWB prime TO UPB prime DO seq sum +:= prime[ i ] OD;
# find the longest sequence that sums to a prime #
INT max start := -1;
INT max end := -1;
INT max len := -1;
INT max sum := -1;
FOR this start FROM LWB prime TO UPB prime - 1 DO
INT this end := UPB prime;
INT this len := ( this end + 1 ) - this start;
IF this len > max len THEN
INT this sum := seq sum;
BOOL this prime := FALSE;
WHILE this end >= this start
AND NOT ( this prime := is prime( this sum ) )
AND this len > max len
DO
this sum -:= prime[ this end ];
this end -:= 1;
this len -:= 1
OD;
IF this prime AND this len > max len THEN
max len := this len; # found a longer sequence #
max start := this start;
max end := this end;
max sum := this sum
FI
FI;
# the start prime won't be in the next sequence #
seq sum -:= prime[ this start ]
OD;
print( ( "Longest sequence of Calmosoft primes up to ", whole( prime[ UPB prime ], 0 )
, " has sum ", whole( max sum, 0 ), " and length ", whole( max len, 0 )
, newline
)
);
FOR i FROM max start TO max end DO print( ( " ", whole( prime[ i ], 0 ) ) ) OD
END
- Output:
Longest sequence of Calmosoft primes up to 97 has sum 953 and length 21 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89
C
#include <stdio.h>
#include <stdbool.h>
#include <string.h>
bool isPrime(int n) {
if (n < 2) return false;
if (n%2 == 0) return n == 2;
if (n%3 == 0) return n == 3;
int d = 5;
while (d*d <= n) {
if (n%d == 0) return false;
d += 2;
if (n%d == 0) return false;
d += 4;
}
return true;
}
int main() {
int primes[30] = {2}, sIndices[5], eIndices[5], sums[5];
int i, j, k, temp, sum, si, ei, pc = 1, longest = 0, count = 0;
for (i = 3; i < 100; i += 2) {
if (isPrime(i)) primes[pc++] = i;
}
for (i = 0; i < pc; ++i) {
for (j = pc-1; j >= i; --j) {
temp = j - i + 1;
if (temp < longest) break;
sum = 0;
for (k = i; k <= j; ++k) sum += primes[k];
if (isPrime(sum)) {
if (temp > longest) {
longest = temp;
count = 0;
}
sIndices[count] = i;
eIndices[count] = j;
sums[count] = sum;
++count;
break;
}
}
}
printf("The longest sequence(s) of CalmoSoft primes having a length of %d is/are:\n\n", longest);
for (i = 0; i < count; ++i) {
si = sIndices[i];
ei = eIndices[i];
sum = sums[i];
for (j = si; j <= ei; ++j) printf("%d + ", primes[j]);
printf("\b\b= %d which is prime\n", sum);
if (i < count - 1) printf("\n");
}
return 0;
}
- Output:
The longest sequence(s) of CalmoSoft primes having a length of 21 is/are: 7 + 11 + 13 + 17 + 19 + 23 + 29 + 31 + 37 + 41 + 43 + 47 + 53 + 59 + 61 + 67 + 71 + 73 + 79 + 83 + 89 = 953 which is prime
Go
package main
import (
"fmt"
"rcu"
"strconv"
)
func main() {
primes := rcu.Primes(100)
pc := len(primes)
longest := 0
var sIndices, eIndices []int
for i := 0; i < pc; i++ {
for j := pc - 1; j >= i; j-- {
temp := j - i + 1
if temp < longest {
break
}
sum := rcu.SumInts(primes[i : j+1])
if rcu.IsPrime(sum) {
if temp > longest {
longest = temp
sIndices = []int{i}
eIndices = []int{j}
} else {
sIndices = append(sIndices, i)
eIndices = append(eIndices, j)
}
break
}
}
}
fmt.Println("The longest sequence(s) of CalmoSoft primes having a length of", longest, "is/are:\n")
for i := 0; i < len(sIndices); i++ {
cp := primes[sIndices[i] : eIndices[i]+1]
sum := rcu.SumInts(cp)
cps := ""
for i := 0; i < len(cp); i++ {
cps += strconv.Itoa(cp[i])
if i < len(cp)-1 {
cps += " + "
}
}
cps += " = " + strconv.Itoa(sum) + " which is prime"
fmt.Println(cps)
if i < len(sIndices)-1 {
fmt.Println()
}
}
}
- Output:
The longest sequence(s) of CalmoSoft primes having a length of 21 is/are: 7 + 11 + 13 + 17 + 19 + 23 + 29 + 31 + 37 + 41 + 43 + 47 + 53 + 59 + 61 + 67 + 71 + 73 + 79 + 83 + 89 = 953 which is prime
Ring
see "works..." + nl
limit = 100
Primes = []
OldPrimes = []
NewPrimes = []
for p = 1 to limit
if isPrime(p)
add(Primes,p)
ok
next
lenPrimes = len(Primes)
for n = 1 to lenPrimes
num = 0
OldPrimes = []
for m = n to lenPrimes
num = num + Primes[m]
add(OldPrimes,Primes[m])
if isPrime(num)
if len(OldPrimes) > len(NewPrimes)
NewPrimes = OldPrimes
ok
ok
next
next
str = "["
for n = 1 to len(NewPrimes)
if n = len(NewPrimes)
str = str + newPrimes[n] + "]"
exit
ok
str = str + newPrimes[n] + ", "
next
sum = 0
strsum = ""
for n = 1 to len(NewPrimes)
sum = sum + newPrimes[n]
if n = len(NewPrimes)
strsum = strsum + newPrimes[n] + " = " + sum + " is prime number"
exit
ok
strsum = strsum + newPrimes[n] + " + "
next
see str + nl
see strsum + nl
see "The longest sequence of CalmoSoft primes = " + len(NewPrimes) + nl
see "done.." + nl
func isPrime num
if (num <= 1) return 0 ok
if (num % 2 = 0 and num != 2) return 0 ok
for i = 3 to floor(num / 2) -1 step 2
if (num % i = 0) return 0 ok
next
return 1
- Output:
works... [7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89] 7 + 11 + 13 + 17 + 19 + 23 + 29 + 31 + 37 + 41 + 43 + 47 + 53 + 59 + 61 + 67 + 71 + 73 + 79 + 83 + 89 = 953 is prime number The longest sequence of CalmoSoft primes = 21 done..
Wren
import "./math" for Int, Nums
var primes = Int.primeSieve(100)
var pc = primes.count
var longest = 0
var sIndices = []
var eIndices = []
for (i in 0...pc) {
for (j in pc-1..i) {
var temp = j - i + 1
if (temp < longest) break
var sum = Nums.sum(primes[i..j])
if (Int.isPrime(sum)) {
if (temp > longest) {
longest = temp
sIndices = [i]
eIndices = [j]
} else {
sIndices.add(i)
eIndices.add(j)
}
break
}
}
}
System.print("The longest sequence(s) of CalmoSoft primes having a length of %(longest) is/are:\n")
for (i in 0...sIndices.count) {
var cp = primes[sIndices[i]..eIndices[i]]
var sum = Nums.sum(cp)
var cps = cp.join(" + ") + " = " + sum.toString + " which is prime"
System.print(cps)
if (i < sIndices.count - 1) System.print()
}
- Output:
The longest sequence(s) of CalmoSoft primes having a length of 21 is/are: 7 + 11 + 13 + 17 + 19 + 23 + 29 + 31 + 37 + 41 + 43 + 47 + 53 + 59 + 61 + 67 + 71 + 73 + 79 + 83 + 89 = 953 which is prime
XPL0
include xpllib; \for IsPrime and Print
int Primes(100), PrimeSums(100);
int I, N, Size, Head, Tail, Longest, Sum, SaveHead, SaveTail;
[I:= 0; \make table of primes
for N:= 2 to 100-1 do
if IsPrime(N) then
[Primes(I):= N; I:= I+1];
Size:= I; \make table of sums
PrimeSums(0):= Primes(0);
for I:= 1 to Size-1 do
PrimeSums(I):= PrimeSums(I-1) + Primes(I);
Longest:= 0; \find longest sequence
for Head:= Size-1 downto 0 do
[Sum:= PrimeSums(Head);
for Tail:= 0 to Head do
[if Head-Tail > Longest then
[if IsPrime(Sum) then
[Longest:= Head-Tail;
SaveHead:= Head;
SaveTail:= Tail;
];
];
Sum:= Sum - Primes(Tail);
];
];
Print( "The longest sequence of CalmoSoft primes < 100 is %d:\n", Longest+1);
Sum:= 0;
for I:= SaveTail to SaveHead do
[Sum:= Sum + Primes(I);
IntOut(0, Primes(I));
if I # SaveHead then ChOut(0, ^+);
];
Print(" = %d\n", Sum);
]
- Output:
The longest sequence of CalmoSoft primes < 100 is 21: 7+11+13+17+19+23+29+31+37+41+43+47+53+59+61+67+71+73+79+83+89 = 953