Help:GeSHi

GeSHi
You are encouraged to solve this task according to the task description, using any language you may know.

The following are examples of typical code formated with GeSHi.

Supported source tags

GeSHi currently supports the following tags: actionscript-french, actionscript, ada, apache, applescript, asm, asp, bash, blitzbasic, caddcl, cadlisp, c_mac, c, cpp, csharp, css, delphi, diff, dos, d, eiffel, freebasic, gml, html4strict, ini, inno, java, javascript, lisp, lua, matlab, mpasm, mysql, nsis, objc, ocaml-brief, ocaml, oobas, oracle8, pascal, perl, php-brief, php, python, qbasic, ruby, scheme, sdlbasic, smarty, sql, vbnet, vb, vhdl, visualfoxpro & xml.

Use trial division. Even numbers may be eliminated right away. A loop from 3 to √(n) will suffice, but other loops are allowed.

Ada

<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;

</Ada>

ALGOL 68

<ALGOL_68>

main:(
  PROC is prime = ( INT n )BOOL:
  (
    IF n = 2 THEN 
      TRUE
    ELIF n <= 1 OR n MOD 2 = 0 THEN 
      FALSE
    ELSE
      BOOL prime := TRUE;
      FOR i FROM 3 BY 2 TO ENTIER sqrt(n) WHILE prime := n MOD i /= 0 DO
         SKIP
      OD;
      prime
    FI
  );
  
  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$)
)

Output: </ALGOL_68>

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

BASIC

Works with: QuickBasic version 4.5

Going with the classic 1 for "true" and 0 for "false": <qbasic>

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

</qbasic>

C

<C> <source 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;
}

</C>

Common Lisp

<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)))

</lisp>

D

<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;
}

</D>

Forth

<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 ;

</Forth>

Haskell

Without square roots: <Haskell>

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..]

</Haskell>

J

Actually 1&p: would do, but the task calls for trial division, so: <J>

isprime=: 3 : 'if. 3>:y do. 1<y else. 0 *./@:< y|~2+i.<.%:y end.'

</J>

Java

<Java>

public static boolean prime(double 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;
}

</Java>

LSE64

<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

</LSE64>

MAXScript

<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
)

</MAXScript>

Perl

<Perl>

sub prime {
  $a = shift;
  if ($a == 2) {
    return 1;
  }
  if ($a <= 1 || $a % 2 == 0) {
    return 0;
  }
  $d = 3;
  while ($d <= sqrt($a)) {
    if ($a % $d == 0) {
      return 0;
    }
    $d += 2;
  }
  return 1;
}

</Perl>

Python

The simplest primality test, using trial division:

Works with: Python version 2.5

<Python> def prime(a):

   return not (a < 2 or any(a % x == 0 for x in range(2, int(a**0.5) + 1)))

</Python>

Another test. Exclude even numbers first:

<Python> 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))

</Python>

Yet another test. Exclude multiples of 2 and 3, see http://www.devx.com/vb2themax/Tip/19051:

Works with: Python version 2.4

<Python> 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

</Python>

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: √ <TI-83 BASIC>

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

</TI-83 BASIC>