Anonymous user
Primality by trial division: Difference between revisions
Scala contribution maintained.
(Scala contribution maintained.) |
|||
Line 3:
;Task:
Write a boolean function that tells whether a given integer is prime.
Remember that '''1''' and all non-positive numbers are not prime.
Line 11 ⟶ 10:
Even numbers over two may be eliminated right away.
A loop from
;Related tasks:
*
*
*
*
*
*
*
*
*
<br><br>
Line 91 ⟶ 90:
END PRIMEDIV</lang>
{{out}}
2 3 5 7 11 13 17 19 23 29 31 37 41 43 47
=={{header|ABAP}}==
Line 244 ⟶ 240:
end Is_Prime;</lang>
As an alternative, one can use the generic function Prime_Numbers.Is_Prime, as specified in [[Prime decomposition#Ada]], which also implements trial division.
<lang Ada>with Prime_Numbers;
Line 276 ⟶ 271:
)</lang>
{{out}}
The primes up to 100 are:
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
=={{header|ALGOL W}}==
Line 305 ⟶ 298:
end.</lang>
{{out}}
2 3 5 7 11 13 17 19 23 29 31
=={{Header|ATS}}==
<lang ATS>(* ****** ****** *)
//
#include
Line 342 ⟶ 332:
) (* end of [is_prime] *)
//
(* ****** ****** *)</lang>
=={{Header|AutoHotkey}}==
Line 432 ⟶ 421:
NEXT n</lang>
{{out}}
==={{header|ZX Spectrum Basic}}===
<lang ZXBasic>10 LET n=0: LET p=0
Line 456 ⟶ 445:
17 is prime!
119 is not prime!
137 is prime!</pre>
=={{header|BBC BASIC}}==
Line 475 ⟶ 463:
= TRUE</lang>
{{out}}
<pre>2 is prime
3 is prime
5 is prime
Line 500 ⟶ 487:
83 is prime
89 is prime
97 is prime</pre>
=={{header|bc}}==
Line 574 ⟶ 560:
=={{header|Burlesque}}==
<lang burlesque>fcL[2==</lang>
Implicit trial division is done by the ''fc'' function. It checks if the number has exactly two divisors.
Line 583 ⟶ 566:
Version not using the ''fc'' function:
<lang burlesque>blsq ) 11^^2\/?dr@.%{0==}ayn!
1
blsq ) 12^^2\/?dr@.%{0==}ayn!
0
blsq ) 13^^2\/?dr@.%{0==}ayn!
1</lang>
Explanation. Given ''n'' generates a block containing ''2..n-1''. Calculates a block of modolus and check if it contains ''0''. If it contains ''0''
it is not a prime.
Line 630 ⟶ 610:
return true;
}</lang>
=={{header|Chapel}}==
Line 650 ⟶ 629:
<lang clojure>(defn divides? [k n] (zero? (mod k n)))</lang>
Testing divisors are in range from
<lang clojure>(defn prime? [x]
(or (= 2 x)
Line 660 ⟶ 639:
Testing only prime divisors:
<lang clojure>(declare prime?)
Line 670 ⟶ 648:
(< 1 x)
(not-any? (partial divides? x)
(take-while (partial >= (Math/sqrt x)) primes)))))</lang>
=={{header|CMake}}==
Line 780 ⟶ 757:
I use [https://franz.com/downloads/clp/survey Allegro CL 10.1]
<lang lisp>;; Project : Primality by trial division
;; Date : 2018/03/06
;; Author : Gal Zsolt [~ CalmoSoft ~]
Line 795 ⟶ 771:
(format t "~d is not a prime number" n)))
(prime 7)
(prime 8)</lang>
Output:
7 is a prime number
=={{header|D}}==
===Simple Version===
Line 822 ⟶ 795:
}</lang>
{{out}}
===Version with excluded multiplies of 2 and 3===
Same output.
Line 872 ⟶ 844:
=={{header|Delphi}}==
=== First ===
<lang Delphi>function IsPrime(aNumber: Integer): Boolean;
Line 930 ⟶ 901:
=={{header|EchoLisp}}==
<lang scheme>(lib 'sequences)
;; Try divisors iff n = 2k + 1
Line 958 ⟶ 928:
(filter is-prime? (range 1 100))
→ (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)</lang>
=={{header|Eiffel}}==
<lang Eiffel>class
APPLICATION
Line 1,018 ⟶ 986:
end
end</lang>
<pre>False
True
True
False
True
False</pre>
=={{header|Elixir}}==
Line 1,042 ⟶ 1,007:
IO.inspect for n <- 1..50, RC.is_prime(n), do: n</lang>
{{out}}
[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47]
=={{header|Emacs Lisp}}==
Use <tt>cl.el</tt> library.
<lang lisp>(defun prime (a)
(not (or (< a 2)
(loop for x from 2 to (sqrt a)
when (zerop (% a x))
return t))))</lang>
More concise, a little bit faster:
<lang lisp>(defun prime2 (a)
(and (> a 1)
(loop for x from 2 to (sqrt a)
never (zerop (% a x)))))</lang>
A little bit faster:
<lang lisp>(defun prime3 (a)
(and (> a 1)
(or (= a 2) (oddp a))
(loop for x from 3 to (sqrt a) by 2
never (zerop (% a x)))))</lang>
More than 2 times faster, than the previous, doesn't use <tt>loop</tt> macro:
<lang lisp>(defun prime4 (a)
(not (or (< a 2)
(some (lambda (x) (zerop (% a x))) (number-sequence 2 (sqrt a))))))</lang>
Almost 2 times faster, than the previous:
<lang lisp>(defun prime5 (a)
(not (or (< a 2)
(and (/= a 2) (evenp a))
(some (lambda (x) (zerop (% a x))) (number-sequence 3 (sqrt a) 2)))))</lang>
=={{header|Erlang}}==
Line 1,094 ⟶ 1,046:
is_prime(N,K) when N rem K == 0 -> false;
is_prime(N,K) -> is_prime(N,K+2).</lang>
=={{header|ERRE}}==
Line 1,119 ⟶ 1,070:
END PROGRAM</lang>
{{out}}
3 is prime
5 is prime
Line 1,144 ⟶ 1,095:
89 is prime
97 is prime
=={{header|Euphoria}}==
Line 1,215 ⟶ 1,165:
NEXT
PAUSE</lang>
{{out}}
Press any key to continue...
=={{header|Forth}}==
Line 1,283 ⟶ 1,232:
{{out}}
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
=={{header|F Sharp|F#}}==
Line 1,315 ⟶ 1,262:
isPrime 277 |> should equal true</lang>
{{out}}
> isPrime 1111111111111111111UL;;
val it : bool = true
and if you want to test really big numbers, use System.Numerics.BigInteger, but it's slower:
<lang fsharp>
Line 1,327 ⟶ 1,273:
let rec test n =
if n * n > x then true else
if x % n = 0I then false else test (n + 2I) in test 3I</lang>
If you have a lot of prime numbers to test, caching a sequence of primes can speed things up considerably, so you only have to do the divisions against prime numbers.
<lang fsharp>let rec primes = Seq.cache(Seq.append (seq[ 2; 3; 5 ]) (Seq.unfold (fun state -> Some(state, state + 2)) 7 |> Seq.filter (fun x -> IsPrime x)))
and IsPrime number =
Line 1,350 ⟶ 1,293:
false
else
IsPrimeCore number 0 number</lang>
=={{header|FunL}}==
Line 1,363 ⟶ 1,305:
(10^10..10^10+50).filter( isPrime ).foreach( println )</lang>
{{out}}
10000000019
10000000033
=={{header|FutureBasic}}==
<lang futurebasic>include "ConsoleWindow"
def tab 6
Line 1,399 ⟶ 1,335:
if j mod 10 == 0 then print
end if
next</lang>
Output:
Prime numbers between 0 and 1000:
2 3 5 7 11 13 17 19 23 29
31 37 41 43 47 53 59 61 67 71
Line 1,420 ⟶ 1,354:
811 821 823 827 829 839 853 857 859 863
877 881 883 887 907 911 919 929 937 941
947 953 967 971 977 983 991 997
=={{header|Gambas}}==
Line 1,452 ⟶ 1,385:
End</lang>
Output:
<pre>1 is prime
3 is prime
5 is prime
Line 1,463 ⟶ 1,395:
83 is prime
89 is prime
97 is prime</pre>
=={{header|GAP}}==
Line 1,532 ⟶ 1,463:
(0..20).grep(isPrime)</lang>
{{out}}
=={{header|Haskell}}==
Line 1,629 ⟶ 1,560:
=={{header|jq}}==
<tt> def is_prime:
if . == 2 then true
else 2 < . and . % 2 == 1 and
Line 1,637 ⟶ 1,567:
| (((($m - 1) / 2) | floor) + 1) as $max
| all( range(1; $max) ; $in % ((2 * .) + 1) > 0 )
end;</tt>
Example -- the command line is followed by alternating lines of input and output:
<tt> $ jq -f is_prime.jq
-2
false
Line 1,650 ⟶ 1,578:
true
100
false</tt>
''Note: if your jq does not have <tt>all</tt>, the following will suffice:''
Line 1,660 ⟶ 1,587:
=={{header|Julia}}==
Julia already has an <tt>isprime</tt> function, so this function has the verbose name <tt>isprime_trialdivision</tt> to avoid overriding the built-in function. Note this function relies on the fact that Julia skips <tt>for</tt>-loops having invalid ranges. Otherwise the function would have to include additional logic to check the odd numbers less than 9.
<lang Julia>function isprime_trialdivision{T<:Integer}(n::T)
1 < n || return false
n != 2 || return true
Line 1,678 ⟶ 1,604:
else
println("The function does not accurately calculate primes.")
end</lang>
{{out}}
The primes <= 100 are:
[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]
=={{header|K}}==
Line 1,705 ⟶ 1,627:
(2..99).filter { isPrime(it) }.forEach { print("$it ") }
}</lang>
{{out}}
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
=={{header|Liberty BASIC}}==
<lang lb>print "Rosetta Code - Primality by trial division"
print
[start]
Line 1,729 ⟶ 1,647:
next i
isPrime=1
end function</lang>
{{out}}
<pre>Rosetta Code - Primality by trial division
Enter an integer: 1
Line 1,740 ⟶ 1,656:
2 is prime
Enter an integer:
Program complete.</pre>
=={{header|Lingo}}==
Line 1,752 ⟶ 1,667:
return TRUE
end</lang>
<lang Lingo>primes = []
repeat with i = 0 to 100
Line 1,758 ⟶ 1,672:
end repeat
put primes</lang>
{{out}}
-- [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]
=={{header|Logo}}==
Line 1,822 ⟶ 1,733:
isprime(11)</lang>
{{out}}
0
1
=={{header|Maple}}==
This could be coded in myriad ways; here is one.
<lang Maple>TrialDivision := proc( n :: integer )
if n <= 1 then
false
Line 1,845 ⟶ 1,753:
true
end if
end proc:</lang>
Using this to pick off the primes up to 30, we get:
<lang Maple>> select( TrialDivision, [seq]( 1 .. 30 ) );
[2, 3, 5, 7, 11, 13, 17, 19, 23, 29]</lang>
Here is a way to check that TrialDivision above agrees with Maple's built-in primality test (isprime).
<lang Maple>> N := 10000: evalb( select( TrialDivision, [seq]( 1 .. N ) ) = select( isprime, [seq]( 1 .. N ) ) );
true</lang>
=={{header|Mathematica}}==
Line 1,994 ⟶ 1,897:
return \isTrue</lang>
{{out}}
<pre>$ java -cp . RCPrimality
List of prime numbers from 1 to 100:
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
Line 2,024 ⟶ 1,926:
List of prime numbers from 100 to -57:
97,89,83,79,73,71,67,61,59,53,47,43,41,37,31,29,23,19,17,13,11,7,5,3,2
Total number of primes: 25</pre>
===[[#REXX|Rexx]] version reimplemented in [[NetRexx]]===
{{trans|REXX}}
Line 2,090 ⟶ 1,991:
for i in 2..30:
echo i, " ", prime(i)</lang>
=={{header|Objeck}}==
Line 2,148 ⟶ 2,048:
=={{header|Oforth}}==
<lang Oforth>Integer method: isPrime
| i |
Line 2,157 ⟶ 2,056:
true ;</lang>
{{out}}
<pre>#isPrime 1000 seq filter println
[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 8
9, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181
Line 2,168 ⟶ 2,066:
, 751, 757, 761, 769, 773, 787, 797, 809, 811, 821, 823, 827, 829, 839, 853, 857, 859, 863
, 877, 881, 883, 887, 907, 911, 919, 929, 937, 941, 947, 953, 967, 971, 977, 983, 991, 997
]</pre>
=={{header|Oz}}==
<lang oz> fun {Prime N}
local IPrime in
fun {IPrime N Acc}
Line 2,184 ⟶ 2,080:
else {IPrime N 2} end
end
end</lang>
=={{header|PARI/GP}}==
Line 2,235 ⟶ 2,130:
end.</lang>
{{out}}
===improved using number wheel===
{{libheader|primTrial}}{{works with|Free Pascal}}
Line 2,252 ⟶ 2,147:
until nextPrime > 50;
end.</lang>
;
=={{header|Perl}}==
Line 2,379 ⟶ 2,274:
}
}
1..15 | foreach{"isPrime $_ : $(isPrime $_)"}</lang>
<b>Output:</b>
<pre>isPrime 1 : False
isPrime 2 : True
isPrime 3 : True
Line 2,397 ⟶ 2,290:
isPrime 13 : True
isPrime 14 : False
isPrime 15 : False</pre>
=={{header|Prolog}}==
Line 2,408 ⟶ 2,300:
M is floor(sqrt(N+1)), % round-off paranoia
Max is (M-1) // 2, % integer division
forall( between(1, Max, I), N mod (2*I+1) > 0 ).</lang>
Example using SWI-Prolog:
<pre>?- time( (bagof( P, (prime(P), ((P > 100000, !, fail); true)), Bag),
Line 2,594 ⟶ 2,485:
97 is prime.
There are 25 primes up to 100 (inclusive).</pre>
===optimized version===
Line 2,678 ⟶ 2,568:
return 1 /*after all that, ··· it's a prime. */</lang>
{{out|output|text= is identical to the first version when the same input is used.}}
=={{header|Ring}}==
<lang ring>give n
flag = isPrime(n)
if flag = 1 see n + " is a prime number"
Line 2,693 ⟶ 2,581:
if (num % i = 0) return 0 ok
next
return 1</lang>
=={{header|Ruby}}==
Line 2,735 ⟶ 2,622:
{{out}}
[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47]
===By Regular Expression===
Line 2,759 ⟶ 2,644:
next i
[exit]
END FUNCTION</lang
2 3 5 7 11 13 17 19 23 25 29 31 37 41 43 47 49
=={{header|Rust}}==
Line 2,776 ⟶ 2,662:
}
}</lang>
{{out}}
<pre>2 is prime!
3 is prime!
Line 2,815 ⟶ 2,699:
print(strjoin(list_to_array(lst), ", "));
}
ptest();</lang>
{{out}}
"2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61"
=={{header|SAS}}==
Line 2,856 ⟶ 2,739:
assert(isPrime(9223372036854775783L)) // Biggest 63-bit prime
assert(!isPrime(Long.MaxValue))</lang>
===Optimized version [[functional_programming|FP]], tail recursion===
Tests 1,2 M numbers against OEIS prime numbers
<lang Scala>import scala.annotation.tailrec
import scala.io.Source
object PrimesTestery extends App {
val rawText = Source.fromURL("https://oeis.org/A000040/a000040.txt")
val oeisPrimes = rawText.getLines().take(100000).map(_.split(" ")(1)).toVector
def isPrime(n: Long) = {
@tailrec
def inner(
if (
else if (n %
}
}
println(oeisPrimes.size)
for (i <- 0 to 1299709) assert(
}</lang>
=={{header|Scheme}}==
Line 2,909 ⟶ 2,801:
end if;
end func;</lang>
Original source: [http://seed7.sourceforge.net/algorith/math.htm#is_prime]
Line 2,920 ⟶ 2,811:
}
}</lang>
{{trans|Perl}}
Alternative version, excluding multiples of 2 and 3:
Line 2,969 ⟶ 2,859:
end</lang>
{{out}}
=={{header|SQL}}==
{{works with|T-SQL}}
<lang tsql>declare @number int
set @number = 514229 -- number to check
Line 3,002 ⟶ 2,891:
' is prime'
end primalityTest
option (maxrecursion 0)</lang>
=={{header|Standard ML}}==
Line 3,018 ⟶ 2,906:
=={{header|Swift}}==
<lang swift>import Foundation
Line 3,146 ⟶ 3,033:
test = prime* <5,6,7></lang>
{{out}}
<true,false,true>
=={{header|V}}==
Line 3,193 ⟶ 3,078:
End Function</lang>
{{out}}
=={{header|VBScript}}==
Line 3,219 ⟶ 3,104:
Next</lang>
{{out}}
=={{header|XPL0}}==
Line 3,238 ⟶ 3,123:
Text(0, "prime^M^J");
until Num = 0</lang>
{{out}}
<pre>777777777
not prime
777777773
is prime
0
not prime</pre>
=={{header|zkl}}==
Line 3,256 ⟶ 3,138:
}</lang>
{{out}}
<pre>zkl: [1..].filter(20,isPrime)
L(2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71)
zkl: isPrime(777777773)
True
zkl: isPrime(777777777)
False</pre>
| |||