Primality by trial division: Difference between revisions
Content added Content deleted
m (Spelling/grammar/aesthetics) |
|||
Line 1: | Line 1: | ||
⚫ | |||
{{task}} |
|||
⚫ | |||
Implement the simplest primality test, using trial division. |
Implement the simplest primality test, using trial division. |
||
Line 78: | Line 76: | ||
=={{header|J}}== |
=={{header|J}}== |
||
Actually<tt> |
Actually <tt>1&p:</tt> would do, but the task calls for trial division, so: |
||
isprime=: 3 : 'if. 3>:y do. 1<y else. 0 *./@:< y|~2+i.<.%:y end.' |
isprime=: 3 : 'if. 3>:y do. 1<y else. 0 *./@:< y|~2+i.<.%:y end.' |
||
Line 187: | Line 185: | ||
Calculator symbol translations: |
Calculator symbol translations: |
||
"STO" arrow: |
"STO" arrow: → |
||
Square root sign: |
Square root sign: √ |
||
Prompt A |
Prompt A |
||
Line 202: | Line 200: | ||
End |
End |
||
1→P |
|||
1→P |
|||
For(B,3, |
For(B,3,√(A)) |
||
If FPart(A/B)=0:Then |
If FPart(A/B)=0:Then |
||
0→P |
|||
0→P |
|||
√(A)→B |
|||
End |
End |
||
B+ |
B+1→B |
||
End |
End |
||
Revision as of 22:18, 20 January 2008
Primality by trial division
You are encouraged to solve this task according to the task description, using any language you may know.
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.
Implement the simplest primality test, using trial division.
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;
BASIC
Compiler: QuickBasic 4.5
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
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; }
Forth
: prime? ( n -- ? ) dup 2 < if drop false else dup 2 = if drop true else dup 1 and 0= if drop false else 3 begin 2dup dup * >= while 2dup mod 0= if 2drop false exit then 2 + repeat 2drop true then then then ;
Haskell
Without square roots:
divides k n = n `mod` k == 0 isPrime :: Integer -> Bool isPrime n | n < 2 = False isPrime n = not $ any (`divides` n) $ takeWhile (\k -> k*k <= n) [2..]
J
Actually 1&p: would do, but the task calls for trial division, so:
isprime=: 3 : 'if. 3>:y do. 1<y else. 0 *./@:< y|~2+i.<.%:y end.'
Java
public static boolean prime(long a){ if(a == 2){ return true; }else if(a <= 1 || a % 2 == 0){ return false; } for(long n= 3; n <= (long)Math.sqrt(a); n+= 2){ if(a % n == 0){ return false; } } return true; }
LSE64
over : 2 pick 2dup : over over even? : 1 & 0 = # trial n d yields "n d 0/1 false" or "n d+2 true" trial : 2 + true trial : 2dup % 0 = then 0 false trial : 2dup dup * < then 1 false trial-loop : trial &repeat # prime? n yields flag prime? : 3 trial-loop >flag drop drop prime? : dup even? then drop false prime? : dup 2 = then drop true prime? : dup 2 < then drop false
MAXScript
fn isPrime n = ( if n == 2 then ( return true ) else if (n <= 1) OR (mod n 2 == 0) then ( return false ) for i in 3 to (sqrt n) by 2 do ( if mod n i == 0 then return false ) true )
Python
The simplest primality test, using trial division:
def prime(a): return not (a < 2 or any(a % x == 0 for x in range(2, int(a**0.5) + 1)))
Another test. Exclude even numbers first:
def prime2(a): if a == 2: return True if a < 2 or a % 2 == 0: return False return not any(a % x == 0 for x in range(3, int(a**0.5) + 1, 2))
Yet another test. Exclude multiples of 2 and 3, see http://www.devx.com/vb2themax/Tip/19051:
def prime3(a): if a < 2: return False if a == 2 or a == 3: return True # manually test 2 and 3 if a % 2 == 0 or a % 3 == 0: return False # exclude multiples of 2 and 3 maxDivisor = a**0.5 d, i = 5, 2 while d <= maxDivisor: if a % d == 0: return False d += i i = 6 - i # this modifies 2 into 4 and viceversa return True
Ruby
def prime(a) if a==2 return true end if a<=1 || a%2==0 return false end d=3 while d <= Math.sqrt(a) do if a%d==0 return false end d+=2 end return true end
TI-83 BASIC
Calculator symbol translations:
"STO" arrow: →
Square root sign: √
Prompt A If A=2:Then Disp "PRIME" Stop End If (fPart(A/2)=0 and A>0) or A<2:Then Disp "NOT PRIME" Stop End 1→P For(B,3,√(A)) If FPart(A/B)=0:Then 0→P √(A)→B End B+1→B End If P=1:Then Disp "PRIME" Else Disp "NOT PRIME" End