Primality by trial division: Difference between revisions

Content added Content deleted

Inline

@@ Line 3,053: / Line 3,053: @@
 =={{header|Picat}}==
-Four different versions:
+Here are four different versions.
+===Iterative===
-* imperative: is_prime1/1 (0.971)
+<lang Picat>is_prime1(N) =>
-* recursive: is_prime2/1 (3.258s)
-* functional: is_prime3/1 (0.938s)
-* testing and generating: prime2/1  (2.129s)  {{trans|Prolog}}
-Times are for calculating the number of primes below 10, 100,1_000,10_000, 100_000, and 1_000_000 respectively.
-<lang Picat>go =>
-  println([I : I in 1..100, is_prime1(I)]),
-  nl,
-  foreach(P in 1..6)
-     Primes = [ I : I in 1..10**P, is_prime1(I)],
-     println([10**P,Primes.len])
-  end,
-  nl.
-% iterative
-is_prime1(N) =>
   if N == 2 then
     true
@@ Line 3,080: / Line 3,064: @@
        N mod I > 0
     end
-  end.
+  end.</lang>
+===Recursive===
-% recursive
-is_prime2(N) =>
+<lang Picat>is_prime2(N) =>
   (N == 2 ; is_prime2b(N,3)).
@@ Line 3,095: / Line 3,079: @@
   ;
     is_prime2b(N,Div+2)
-  ).
+  ).</lang>
-% Functional
+===Functional===
-is_prime3(2) => true.
+<lang Picat>is_prime3(2) => true.
 is_prime3(3) => true.
 is_prime3(P) => P > 3, P mod 2 =\= 0, not has_factor3(P,3).
 has_factor3(N,L), N mod L == 0 => true.
-has_factor3(N,L) => L * L < N, L2 = L + 2, has_factor3(N,L2).
+has_factor3(N,L) => L * L < N, L2 = L + 2, has_factor3(N,L2).</lang>
+===Generator approach===
+{{trans|Prolog}}
+<code>prime2(N)</code> can be used to generate primes until memory is exhausted.
+Difference from Prolog implementation: Picat does not support <code>between/3</code> with
-% Translation of Prolog version.
+"inf" as upper bound, so a high number (here 2**156+1) must be used.
-% prime2(N) can be used to generate primes until memory is exhausted
+<lang Picat>prime2(2).
-%
-% Difference from Prolog implementation: Picat does not support between/3 with
-% "inf" as upper bound, so a high number (here 2**156+1) must be used.
-prime2(2).
 prime2(N) :-
   between(3, 2**156+1, N),
@@ Line 3,118: / Line 3,102: @@
   Max is (M-1) // 2,        % integer division
   foreach(I in 1..Max) N mod (2*I+1) > 0 end.</lang>
+===Test===
+<lang Picat>go =>
+  println([I : I in 1..100, is_prime1(I)]),
+  nl,
+  foreach(P in 1..6)
+     Primes = [ I : I in 1..10**P, is_prime1(I)],
+     println([10**P,Primes.len])
+  end,
+  nl.</lang>
 {{out}}
@@ Line 3,128: / Line 3,123: @@
 [100000,9592]
 [1000000,78498]</pre>
+===Benchmark===
+Times for calculating the number of primes below 10, 100,1_000,10_000, 100_000, and 1_000_000 respectively.
+* imperative: <code>is_prime1/1</code> (0.971)
+* recursive: <code>is_prime2/1</code> (3.258s)
+* functional: <code>is_prime3/1</code> (0.938s)
+* test/generate <code>prime2/1</code>  (2.129s)
 =={{header|PicoLisp}}==