Primality by trial division
You are encouraged to solve this task according to the task description, using any language you may know.
Write a boolean function that tells whether a given integer is prime. Remember that 1 and all non-positive numbers are not prime.
Use trial division. Even numbers may be eliminated right away. A loop from 3 to √(n) will suffice, but other loops are allowed.
Ada
<lang ada>function Is_Prime(Item : Positive) return Boolean is
Result : Boolean := True; Test : Natural;
begin
if Item /= 2 and Item mod 2 = 0 then
Result := False;
else
Test := 3;
while Test < Integer(Sqrt(Float(Item))) loop
if Item mod Test = 0 then
Result := False;
exit;
end if;
Test := Test + 2;
end loop;
end if;
return Result;
end Is_Prime;</lang>
ALGOL 68
<lang algol68>main:(</lang>
COMMENT This routine is used in more than one place, and is essentially a template that can by used for many different types, eg INT, LONG INT... USAGE MODE ISPRIMEINT = INT, LONG INT, etc PR READ "prelude/is_prime.a68" PR END COMMENT
PROC is prime = ( ISPRIMEINT p )BOOL:
IF p <= 1 OR ( NOT ODD p AND p/= 2) THEN
FALSE
ELSE
BOOL prime := TRUE;
FOR i FROM 3 BY 2 TO ENTIER sqrt(p)
WHILE prime := p MOD i /= 0 DO SKIP OD;
prime
FI
<lang algol68> INT upb=100;
printf(($" The primes up to "g(-3)" are:"l$,upb));
FOR i TO upb DO
IF is prime(i) THEN
printf(($g(-4)$,i))
FI
OD;
printf($l$)
)</lang> Output: <lang algol68>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</lang>
AutoHotkey
Discussion <lang autohotkey>MsgBox % IsPrime(1995937) Loop
MsgBox % A_Index-3 . " is " . (IsPrime(A_Index-3) ? "" : "not ") . "prime."
IsPrime(n,k=2) { ; testing primality with trial divisors not multiple of 2,3,5, up to sqrt(n)
d := k+(k<7 ? 1+(k>2) : SubStr("6-----4---2-4---2-4---6-----2",Mod(k,30),1))
Return n < 3 ? n>1 : Mod(n,k) ? (d*d <= n ? IsPrime(n,d) : 1) : 0
}</lang>
AWK
$ awk 'func prime(n){for(d=2;d<=sqrt(n);d++)if(!(n%d)){return 0};return 1}{print prime($1)}'
BASIC
Going with the classic 1 for "true" and 0 for "false":
FUNCTION prime% (n!)
IF n = 2 THEN prime = 1
IF n <= 1 OR n MOD 2 = 0 THEN prime = 0
FOR a = 3 TO INT(SQR(n)) STEP 2
IF n MOD a = 0 THEN prime = 0
NEXT a
prime = 1
END FUNCTION
C
<lang c>#include <math.h>
- define FALSE 0
- define TRUE 1
int isPrime( unsigned int n ) {
unsigned int i;
if ( n == 2 )
return TRUE;
if ( n <= 1 || ( n & 1 ) == 0 )
return FALSE;
for ( i = 3 ; i <= sqrt( n ) ; i += 2 )
if ( n % i == 0 )
return FALSE;
return TRUE;
}</lang>
C++
<lang cpp>#include <cmath>
bool is_prime(unsigned int n) {
if (n <= 1)
return false;
if (n == 2)
return true;
for (unsigned int i = 2; i <= sqrt(n); ++i)
if (n % i == 0)
return false;
return true;
}</lang>
Clojure
The symbol # is a shortcut for creating lambda functions; the arguments in such a function are %1, %2, %3... (or simply % if there is only one argument). Thus, #(< (* % %) n) is equivalent to (fn [x] (< (* x x) n)) or more mathematically f(x) = x * x < n.
(defn divides? [k n] (= (rem n k) 0))
(defn prime? [n]
(if (< n 2)
false
(empty? (filter #(divides? % n) (take-while #(<= (* % %) n) (range 2 n))))))
Common Lisp
<lang Lisp>
(defun primep (a)
(cond ((= a 2) T)
((or (<= a 1) (= (mod a 2) 0)) nil)
((loop for i from 3 to (sqrt a) by 2 do
(if (= (mod a i) 0)
(return nil))) nil)
(T T)))
</lang> <lang Lisp> (defun primep (n)
"Is N prime?"
(and (> n 1)
(or (= n 2) (oddp n))
(loop for i from 3 to (isqrt n) by 2
never (zerop (rem n i))))) </lang>
D
<lang d>import std.math: sqrt; bool isPrime(int n) {
if (n == 2)
return true;
if (n <= 1 || (n & 1) == 0)
return false;
for(int i = 3; i <= sqrt(cast(float)n); i += 2)
if (n % i == 0)
return false;
return true;
}</lang>
Version with excluded multiplies of 2 and 3
<lang d>/**
* to compile: * $ dmd -run prime_trial.d * to optimize: * $ dmd -O -inline -release prime_trial.d */
module prime_trial;
import std.conv