Find prime numbers of the form n*n*n+2: Difference between revisions
m (→{{header|Julia}}: add brief version) |
|||
| Line 231: | Line 231: | ||
The total found was 19. |
The total found was 19. |
||
</pre> |
</pre> |
||
=== One-liner version === |
|||
<lang julia>using Primes; println(filter(isprime, map(x -> x^3 + 2, 1:199)))</lang>{{out}}<pre> |
|||
[3, 29, 127, 24391, 91127, 250049, 274627, 328511, 357913, 571789, 1157627, 1442899, 1860869, 2146691, 2924209, 3581579, 5000213, 5177719, 6751271]</pre> |
|||
=={{header|Phix}}== |
=={{header|Phix}}== |
||
Revision as of 04:23, 16 March 2021
- Task
- Find prime numbers of the form n3+2, where 0 < n < 200
C
<lang c>#include <stdio.h>
- include <stdbool.h>
- include <locale.h>
bool isPrime(int n) {
int d;
if (n < 2) return false;
if (!(n%2)) return n == 2;
if (!(n%3)) return n == 3;
d = 5;
while (d*d <= n) {
if (!(n%d)) return false;
d += 2;
if (!(n%d)) return false;
d += 4;
}
return true;
}
int main() {
int n, p;
const int limit = 200;
setlocale(LC_ALL, "");
for (n = 1; n < limit; ++n) {
p = n*n*n + 2;
if (isPrime(p)) {
printf("n = %3d => n³ + 2 = %'9d\n", n, p);
}
}
return 0;
}</lang>
- Output:
n = 1 => n³ + 2 = 3 n = 3 => n³ + 2 = 29 n = 5 => n³ + 2 = 127 n = 29 => n³ + 2 = 24,391 n = 45 => n³ + 2 = 91,127 n = 63 => n³ + 2 = 250,049 n = 65 => n³ + 2 = 274,627 n = 69 => n³ + 2 = 328,511 n = 71 => n³ + 2 = 357,913 n = 83 => n³ + 2 = 571,789 n = 105 => n³ + 2 = 1,157,627 n = 113 => n³ + 2 = 1,442,899 n = 123 => n³ + 2 = 1,860,869 n = 129 => n³ + 2 = 2,146,691 n = 143 => n³ + 2 = 2,924,209 n = 153 => n³ + 2 = 3,581,579 n = 171 => n³ + 2 = 5,000,213 n = 173 => n³ + 2 = 5,177,719 n = 189 => n³ + 2 = 6,751,271
Factor
Using the parity optimization from the Wren entry:
<lang factor>USING: formatting kernel math math.functions math.primes math.ranges sequences tools.memory.private ;
1 199 2 <range> [
dup 3 ^ 2 + dup prime? [ commas "n = %3d => n³ + 2 = %9s\n" printf ] [ 2drop ] if
] each</lang> Or, using local variables:
<lang factor>USING: formatting kernel math math.primes math.ranges sequences tools.memory.private ;
[let
199 :> limit
1 limit 2 <range> [| n |
n n n * * 2 + :> p
p prime?
[ n p commas "n = %3d => n³ + 2 = %9s\n" printf ] when
] each
]</lang>
- Output:
n = 1 => n³ + 2 = 3 n = 3 => n³ + 2 = 29 n = 5 => n³ + 2 = 127 n = 29 => n³ + 2 = 24,391 n = 45 => n³ + 2 = 91,127 n = 63 => n³ + 2 = 250,049 n = 65 => n³ + 2 = 274,627 n = 69 => n³ + 2 = 328,511 n = 71 => n³ + 2 = 357,913 n = 83 => n³ + 2 = 571,789 n = 105 => n³ + 2 = 1,157,627 n = 113 => n³ + 2 = 1,442,899 n = 123 => n³ + 2 = 1,860,869 n = 129 => n³ + 2 = 2,146,691 n = 143 => n³ + 2 = 2,924,209 n = 153 => n³ + 2 = 3,581,579 n = 171 => n³ + 2 = 5,000,213 n = 173 => n³ + 2 = 5,177,719 n = 189 => n³ + 2 = 6,751,271
Go
<lang go>package main
import "fmt"
func isPrime(n int) bool {
switch {
case n < 2:
return false
case n%2 == 0:
return n == 2
case n%3 == 0:
return n == 3
default:
d := 5
for d*d <= n {
if n%d == 0 {
return false
}
d += 2
if n%d == 0 {
return false
}
d += 4
}
return true
}
}
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() {
const limit = 200
for n := 1; n < limit; n++ {
p := n*n*n + 2
if isPrime(p) {
fmt.Printf("n = %3d => n³ + 2 = %9s\n", n, commatize(p))
}
}
}</lang>
- Output:
n = 1 => n³ + 2 = 3 n = 3 => n³ + 2 = 29 n = 5 => n³ + 2 = 127 n = 29 => n³ + 2 = 24,391 n = 45 => n³ + 2 = 91,127 n = 63 => n³ + 2 = 250,049 n = 65 => n³ + 2 = 274,627 n = 69 => n³ + 2 = 328,511 n = 71 => n³ + 2 = 357,913 n = 83 => n³ + 2 = 571,789 n = 105 => n³ + 2 = 1,157,627 n = 113 => n³ + 2 = 1,442,899 n = 123 => n³ + 2 = 1,860,869 n = 129 => n³ + 2 = 2,146,691 n = 143 => n³ + 2 = 2,924,209 n = 153 => n³ + 2 = 3,581,579 n = 171 => n³ + 2 = 5,000,213 n = 173 => n³ + 2 = 5,177,719 n = 189 => n³ + 2 = 6,751,271
Julia
<lang julia># Formatting output as in Go example. using Primes, Formatting
isncubedplus2prime(x) = begin fx = x * x * x + 2; (isprime(fx), fx) end
tostring(x, fx) = "n = " * lpad(x, 3) * " => n³ + 2 =" * lpad(format(fx, commas=true), 10)
function filterprintresults(x_to_bool_and_fx, start, stop, stringify=(x, fx)->"$x $fx", doprint=true)
ncount = 0
println("Filtering $x_to_bool_and_fx for integers between $start and $stop:\n")
for n in start+1:stop-1
isone, result = x_to_bool_and_fx(n)
if isone
doprint && println(stringify(n, result))
ncount += 1
end
end
println("\nThe total found was $ncount.")
end
filterprintresults(isncubedplus2prime, 0, 200, tostring)
</lang>
- Output:
n = 1 => n³ + 2 = 3 n = 3 => n³ + 2 = 29 n = 5 => n³ + 2 = 127 n = 29 => n³ + 2 = 24,391 n = 45 => n³ + 2 = 91,127 n = 63 => n³ + 2 = 250,049 n = 65 => n³ + 2 = 274,627 n = 69 => n³ + 2 = 328,511 n = 71 => n³ + 2 = 357,913 n = 83 => n³ + 2 = 571,789 n = 105 => n³ + 2 = 1,157,627 n = 113 => n³ + 2 = 1,442,899 n = 123 => n³ + 2 = 1,860,869 n = 129 => n³ + 2 = 2,146,691 n = 143 => n³ + 2 = 2,924,209 n = 153 => n³ + 2 = 3,581,579 n = 171 => n³ + 2 = 5,000,213 n = 173 => n³ + 2 = 5,177,719 n = 189 => n³ + 2 = 6,751,271 The total found was 19.
One-liner version
<lang julia>using Primes; println(filter(isprime, map(x -> x^3 + 2, 1:199)))</lang>
- Output:
[3, 29, 127, 24391, 91127, 250049, 274627, 328511, 357913, 571789, 1157627, 1442899, 1860869, 2146691, 2924209, 3581579, 5000213, 5177719, 6751271]
Phix
<lang Phix>function pn3p2(integer n)
integer n3p2 = power(n,3)+2
return iff(is_prime(n3p2)?{n,n3p2}:0)
end function sequence res = filter(apply(tagset(199,1,2),pn3p2),"!=",0) printf(1,"Found %d primes of the form n^3+2:\n",length(res)) papply(true,printf,{1,{"n = %3d => n^3+2 = %,9d\n"},res})</lang>
- Output:
Found 19 primes of the form n^3+2: n = 1 => n^3+2 = 3 n = 3 => n^3+2 = 29 n = 5 => n^3+2 = 127 n = 29 => n^3+2 = 24,391 n = 45 => n^3+2 = 91,127 n = 63 => n^3+2 = 250,049 n = 65 => n^3+2 = 274,627 n = 69 => n^3+2 = 328,511 n = 71 => n^3+2 = 357,913 n = 83 => n^3+2 = 571,789 n = 105 => n^3+2 = 1,157,627 n = 113 => n^3+2 = 1,442,899 n = 123 => n^3+2 = 1,860,869 n = 129 => n^3+2 = 2,146,691 n = 143 => n^3+2 = 2,924,209 n = 153 => n^3+2 = 3,581,579 n = 171 => n^3+2 = 5,000,213 n = 173 => n^3+2 = 5,177,719 n = 189 => n^3+2 = 6,751,271
Raku
<lang perl6># 20210315 Raku programming solution
say ((1…199)»³ »+»2).grep: *.is-prime</lang>
- Output:
(3 29 127 24391 91127 250049 274627 328511 357913 571789 1157627 1442899 1860869 2146691 2924209 3581579 5000213 5177719 6751271)
REXX
Since REXX doesn't have a isPrime function, this REXX program generates a number of primes such that some
numbers can be tested for primality directly, other numbers have to be tested by trial division for primality.
A suitable number was calculated to generate a number of primes such that about half of the computing time used to
test the numbers for primality could be directly determined their primality, the other half of the computing time used
would use trial division.
Since the task's requirements are pretty straight-forward and easy, a little extra code was added for presentation
(title and title separator line, the count of primes found, and commatization of the numbers).
<lang rexx>/*REXX program finds and displays n primes of the form: n**3 + 2. */
parse arg LO HI hp . /*obtain optional argument from the CL.*/
if LO== | LO=="," then LO= 0 /*Not specified? Then use the default.*/
if HI== | HI=="," then HI= 200 /* " " " " " " */
if hp== | hp=="," then hp= 19 /* " " " " " " */
h= max(iSqrt(HI**3), hp**3) /*a high prime to generate primes to. */
w= length( commas(HI**3) ) + 3
call genP /*build array of semaphores for primes.*/
say right('n', 20) ' (n**3 + 2)' /*display a title for the output list. */
say left(, 20 + w + 20, '─') /*display a sep for the output list. */
finds= 0 /*# of triplet strange primes (so far).*/
do j=LO+1 by 2 to HI-1 /*look for primes of form of: n**3 + 2 */
x= j**3 + 2
if x<=@.# then if \!.x then iterate /*Not a semaphore prime? Then skip it.*/
else nop /*the NOP matches up with the "THEN".*/
else do k=2 while @.k**2<=x /*perform a primality test by division.*/
if x//@.k==0 then iterate j
end /*k*/
finds= finds + 1 /*bump # primes found of form: n**3+2 */
say right(commas(j), 20) right( commas(x), w)
end /*j*/
say left(, 20 + w + 20, '─'); say /*display a sep for the output list. */ say 'Found ' commas(finds) ' primes in the form of: n**3 + 2' exit 0 /*stick a fork in it, we're all done. */ /*──────────────────────────────────────────────────────────────────────────────────────*/ commas: parse arg ?; do jc=length(?)-3 to 1 by -3; ?=insert(',', ?, jc); end; return ? /*──────────────────────────────────────────────────────────────────────────────────────*/ iSqrt: procedure; parse arg x; r=0; q=1; do while q<=x; q=q*4; end
do while q>1; q=q%4; _=x-r-q; r=r%2; if _>=0 then do;x=_;r=r+q; end; end
return r
/*──────────────────────────────────────────────────────────────────────────────────────*/ genP: !.= 0; pad= left(, 9) /*placeholders for primes; width of #'s*/
@.1=2; @.2=3; @.3=5; @.4=7; @.5=11 /*define some low primes. */
!.2=1; !.3=1; !.5=1; !.7=1; !.11=1 /* " " " " flags. */
#=5; s.#= @.# **2 /*number of primes so far; prime². */
/* [↓] generate more primes ≤ h. */
do j=@.#+2 by 2 to h /*find odd primes from here on. */
parse var j -1 _; if _==5 then iterate /*J divisible by 5? (right dig)*/
if j// 3==0 then iterate /*" " " 3? */
if j// 7==0 then iterate /*" " " 7? */
/* [↑] the above five lines saves time*/
do k=5 while s.k<=j /* [↓] divide by the known odd primes.*/
if j // @.k == 0 then iterate j /*Is J ÷ X? Then not prime. ___ */
end /*k*/ /* [↑] only process numbers ≤ √ J */
#= #+1; @.#= j; s.#= j*j; !.j= 1 /*bump # of Ps; assign next P; P²; P# */
end /*j*/; return</lang>
- output when using the default inputs:
n (n**3 + 2)
────────────────────────────────────────────────────
1 3
3 29
5 127
29 24,391
45 91,127
63 250,049
65 274,627
69 328,511
71 357,913
83 571,789
105 1,157,627
113 1,442,899
123 1,860,869
129 2,146,691
143 2,924,209
153 3,581,579
171 5,000,213
173 5,177,719
189 6,751,271
────────────────────────────────────────────────────
Found 19 primes in the form of: n**3 + 2
Ring
<lang ring> load "stdlib.ring"
see "working..." + nl
for n = 1 to 200 step 2
pr = pow(n,3)+2
if isprime(pr)
see "n = " + n + " => n³+2 = " + pr + nl
ok
next
see "done..." + nl </lang>
- Output:
working... n = 1 => n³+2 = 3 n = 3 => n³+2 = 29 n = 5 => n³+2 = 127 n = 29 => n³+2 = 24391 n = 45 => n³+2 = 91127 n = 63 => n³+2 = 250049 n = 65 => n³+2 = 274627 n = 69 => n³+2 = 328511 n = 71 => n³+2 = 357913 n = 83 => n³+2 = 571789 n = 105 => n³+2 = 1157627 n = 113 => n³+2 = 1442899 n = 123 => n³+2 = 1860869 n = 129 => n³+2 = 2146691 n = 143 => n³+2 = 2924209 n = 153 => n³+2 = 3581579 n = 171 => n³+2 = 5000213 n = 173 => n³+2 = 5177719 n = 189 => n³+2 = 6751271 done...
Wren
If n is even then n³ + 2 is also even, so we only need to examine odd values of n here. <lang ecmascript>import "/math" for Int import "/trait" for Stepped import "/fmt" for Fmt
var limit = 200 for (n in Stepped.new(1...limit, 2)) {
var p = n*n*n + 2
if (Int.isPrime(p)) Fmt.print("n = $3d => n³ + 2 = $,9d", n, p)
}</lang>
- Output:
n = 1 => n³ + 2 = 3 n = 3 => n³ + 2 = 29 n = 5 => n³ + 2 = 127 n = 29 => n³ + 2 = 24,391 n = 45 => n³ + 2 = 91,127 n = 63 => n³ + 2 = 250,049 n = 65 => n³ + 2 = 274,627 n = 69 => n³ + 2 = 328,511 n = 71 => n³ + 2 = 357,913 n = 83 => n³ + 2 = 571,789 n = 105 => n³ + 2 = 1,157,627 n = 113 => n³ + 2 = 1,442,899 n = 123 => n³ + 2 = 1,860,869 n = 129 => n³ + 2 = 2,146,691 n = 143 => n³ + 2 = 2,924,209 n = 153 => n³ + 2 = 3,581,579 n = 171 => n³ + 2 = 5,000,213 n = 173 => n³ + 2 = 5,177,719 n = 189 => n³ + 2 = 6,751,271