"Check the Number is Prime" in every Programming Language

[Canis familiaris]

First of all my apologies for literally stealing the idea from this thread (http://ubuntuforums.org/showthread.php?t=497579) which I found very interesting. However a "Hello Ubuntu" program will lack the concept of conditions and iterations, so I wondered it would be great to have a thread which would showcase these concepts in every programming language. So This is the thread for program which will:
(1) Get a number as User Input.
(2) Determine whether the number is Prime or Not and hence display the output.
I guess it would be interesting to see :), particularly how iterations are implmented in programming languages which do not have loops.
Also Rules:
(1) Do Not Use a Built in Function for determining a prime.
(2) The code should be clean.
(3) Use this site (http://www.challenge-you.com/bbcode) so that you can use the [CODE] tags to have syntax highlighting. Unfortunately I don't think [PHP] tag would really suffice IMO except for PHP of course.
(4) You can post in languages already posted, but a different algorithm would be appreciated.
(5) Please specify the programming language.

Thanks.

[Canis familiaris]

My Entries:
Python


#!/usr/bin/python
num = input('Enter the number which you wish to determine it is prime: ')

if num < 2:
print "\nThe Number", num, " is not a prime!"
else:
for div in range(2, (num/2)+1):
if num%div==0:
print "\nThe Number", num, " is not a prime!"
break
else:
print "\nThe Number", num, " is a prime!"


C

#include<stdio.h>

int main()
{
int div;
int num;

printf("Enter a number: ");
scanf("%d", &num);

if(num>=2)
for(div=2; div <= num/2; div++)
if((num%div)==0)
break;

if(num>1 && (!(div<=num/2)))
printf("\nThe number %d is a prime.", num);
else
printf("\nThe number %d is not a prime", num);

return 0;
}



C++

#include<iostream>
using namespace std;

int main()
{
int div;
int num;

cout<<"Enter a number: ";
cin>>num;

if(num>=2)
for(div=2; div <= num/2; div++)
if((num%div)==0)
break;

if(num>1 && (!(div<=num/2)))
cout<<"The number "<<num<<" is a prime\n";
else
cout<<"The number "<<num<<" is not a prime\n";


return 0;
}

Special Thanks to Reiger for correcting the Code in C and C++


I am a newbie in programming, particularly Python, so please highlight my mistakes and give tips.

[Borusa]

Just a note - you only need to go up to the square root of the number, not above (well, for the sake of your code, one above the square root will make better sense).

Ideally, you would only need to do the division for prime numbers below the square root of the number, but I can't work out a way of doing that that's actually less expensive than doing it your way.

[Canis familiaris]

Just a note - you only need to go up to the square root of the number, not above (well, for the sake of your code, one above the square root will make better sense).

Ideally, you would only need to do the division for prime numbers below the square root of the number, but I can't work out a way of doing that that's actually less expensive than doing it your way.

Thanks but I don't think it will make much difference since the loop will terminate when it finds the lowest factor.
Good Idea, neverthless.

Though I think the best implementation would be the loop to list prime number and check the divisibility. This would result in a much more efficient cycle. But I am not sure how to implement it.


Python

#!/usr/bin/python
num = input('Enter the number which you wish to determine it is prime: ')

for div in range(2, (num/2)+1):
if num%div==0:
print "\nThe Number", num, " is not a prime!"
break
else:
print "\nThe Number", num, " is a prime!"


Also I was wondering is there a way to have the last number in the range() to be inclusive rather than exclusive in Python. I am not really liking the statement (num/2)+1.

[Reiger]

A quick Haskell version:

module Test where
import Char

getInput i = (putStrLn i) >> getLine

run i = do
s <- getInput i
if (all isDigit s)
then (return (read s :: Integer))
else (run "That's not a Positive Integer, and therefore it cannot possibly be prime! Please try again:")

primes (x:xs) = x : ( primes $ filter (`isRelativePrimeTo` x) xs )
primes x = x

isRelativePrimeTo = \x y -> x `mod` y /= 0


isPrime q = and $ map (q `isRelativePrimeTo`) $ primes $ [2..(floor $ sqrt $ fromInteger q)]

main = do
q <- (run "Please enter the number which might be prime:")
if ((q>1) && (isPrime q))
then (putStrLn $ "Indeed, "++(show q)++" is prime!")
else (putStrLn $ "No, "++(show q)++" is not prime!")

Optimised a little. ;)

[Idefix82]

In the C and C++ versions you are only checking whether the number is even. You want to replace num%2 by num%dev.

[Canis familiaris]

In the C and C++ versions you are only checking whether the number is even. You want to replace num%2 by num%dev.

Oops! My mistake. I think I posted the wrong Code.
I guess this is some indication I'm out of practice.
:P

[geirha]

#!/bin/bash

# Simple way of approximating the square root using integer arithmetics
sqrt() # $1 - number
{
local i=1 j=1 n=$1
while (( i*i <= n )); do
((j=i, i++))
done
echo "$j"
}

isprime() # $1 - number
{
local i=3 n=$1 h=0

# Only considering 2 or greater
(( n >= 2 )) || return

# Trivial cases
(( n == 2 || n == 3 )) && return

(( n % 2 == 0 )) && return 1
h=$(( $(sqrt "$n") + 1 ))
while (( i < h )); do
(( n % i == 0 )) && return 1
(( i += 2 ))
done
return 0
}


# If no arguments are given, prompt for an integer
if (( $# == 0 )); then
read -p "Enter integer number: " n || exit
else
n=$1
fi

if isprime "$n"; then
echo "$n is prime"
else
echo "$n is not prime"
fi

[slavik]

Perl. :)



#!/usr/bin/perl
use strict;
use warnings;

sub isprime {
my $num = shift;
if ($num < 2) return false;
if ($num == 2) return true;
else for (my $i = 2; $i < sqrt($num); $i++) { if ($num % $i == 0) return false; }
return true;
}

while (<>) {
if (isprime($_)) {
print $_ . " is prime\n";
}
else print $_ . " is not prime\n";
}

[kknd]

Lua


local number = io.read("*n")
local isPrime = true

for i = 2, math.sqrt(number) do
if number % i == 0 then
isPrime = false
break
end
end

if isPrime then print("Is prime!") else print("Isn't prime!") end

[jespdj]

Ruby

#!/usr/bin/env ruby

class PrimeGen
attr_reader :primes

def initialize
@primes = [2, 3]
end

def generate_next
def check_prime(n)
limit = Math.sqrt(n).ceil
@primes.each {|p| break false if n % p == 0; break true unless p < limit }
end

n = @primes[-1] + 2
n += 2 until check_prime(n)
@primes << n
return n
end
end

print "Enter a number: "
num = gets.to_i

p = PrimeGen.new
p.generate_next until p.primes[-1] >= num

if num == 2 or p.primes[-1] == num then puts "#{num} is prime" else puts "#{num} is composite" end

Partly copied and pasted from one of my Project Euler (http://projecteuler.net/) programs.

[NovaAesa]

Befunge


25v v p 05 +1g 05 <
v0< >: 50 g%|
>p>&>:50g`|@,,"!p"<
@ , "p" <


Gotta love those esoteric languages (and yes, I did write this code myself).

[Reiger]

My Entries:
C

#include<stdio.h>

int main()
{
int div;
int num;

printf("Enter a number: ");
scanf("%d", &num);


for(div=2; div<=num/2; div++)
{
if(num%div==0)
{
printf("\nThe Number %d is not a prime\n", num);
break;
}
}

if(!(div<num/2))
printf("\nThe Number %d is a prime\n", num);

return 0;
}


C++


#include<iostream>
using namespace std;

int main()
{
int div;
int num;

cout<<"Enter a number: ";
cin>>num;


for(div=2; div<=num/2; div++)
{
if(num%div==0)
{
cout<<"The number "<<num<<" is not a prime\n";
break;
}
}

if(!(div<num/2))
cout<<"The number "<<num<<" is a prime\n";

return 0;
}


I am a newbie in programming, particularly Python, so please highlight my mistakes and give tips.

These entries are not 'valid' as they do report incorrect results:


prometheus@Bartix:~/Documents$ gcc -o test prime.c
prometheus@Bartix:~/Documents$ chmod +x test
prometheus@Bartix:~/Documents$ ./test
Enter a number: 0

The Number 0 is a prime
prometheus@Bartix:~/Documents$ ./test
Enter a number: 1

The Number 1 is a prime


Proved with your C version, but since you apply the same algorith and therefore the same bug to your C++ version; both will not work. The same thing can be shown for negative input. The reason is that you assume all primes will have been filtered out if and only if your for loop has been 'fully' executed, without any forced breaks. But the for loop will never be executed at all if the input is less than 2, yet your if-condition will dutifully ('div' having been set to 2, which is more than the input!) evaluate to true, and hence your program is tricked into believing anything less than 2 is prime.

[Canis familiaris]

These entries are not 'valid' as they do report incorrect results:


prometheus@Bartix:~/Documents$ gcc -o test prime.c
prometheus@Bartix:~/Documents$ chmod +x test
prometheus@Bartix:~/Documents$ ./test
Enter a number: 0

The Number 0 is a prime
prometheus@Bartix:~/Documents$ ./test
Enter a number: 1

The Number 1 is a prime


Proved with your C version, but since you apply the same algorith and therefore the same bug to your C++ version; both will not work. The same thing can be shown for negative input. The reason is that you assume all primes will have been filtered out if and only if your for loop has been 'fully' executed, without any forced breaks. But the for loop will never be executed at all if the input is less than 2, yet your if-condition will dutifully ('div' having been set to 2, which is more than the input!) evaluate to true, and hence your program is tricked into believing anything less than 2 is prime.

Thanks. Noted. Will Correct it.

EDIT: Done. Is it OK Now?

[Reiger]

Ehrm no. As a matter of fact you have now made it explicit that your program should believe everything below 2 is prime:


if((!(div<num/2)) || num < 2)

Whereas anything below 2 cannot possibly be prime, so I think you meant:


if(num>1 && (!(div<num/2)))


EDIT: And there's more:


prometheus@Bartix:~/Documents$ gcc -o test prime.c
prometheus@Bartix:~/Documents$ chmod +x test
prometheus@Bartix:~/Documents$ ./test
Enter a number: 4

The Number 4 is not a prime

The Number 4 is a prime


Previously tested it with 27, which goes OK, but 4 is even so...



if(num>1 && (!(div<=num/2)))


Should be the condition. Now for a minor touch up:

#include<stdio.h>

int main()
{
int div;
int num;

printf("Enter a number: ");
scanf("%d", &num);

if(num>=2)
for(div=2; div<=num/2; div++)
if(num%div==0)
break;

if(num>1 && (!(div<=num/2)))
printf("\nThe Number %d is a prime\n", num);
else
printf("\nThe Number %d is not a prime\n", num);

return 0;
}


EDIT: The touch-up thing is ensuring that the program gives output in the rare (previously broken) cases. For instance, running the programatically-fixed version with input 0 wouldn't yield any output as no printf() call could be reached. So I restructured the code to make all non-primes fall into the else clause.

[Canis familiaris]

Ehrm no. As a matter of fact you have now made it explicit that your program should believe everything below 2 is prime:


if((!(div<num/2)) || num < 2)

Whereas anything below 2 cannot possibly be prime, so I think you meant:


if(num>1 && (!(div<num/2)))


EDIT: And there's more:


prometheus@Bartix:~/Documents$ gcc -o test prime.c
prometheus@Bartix:~/Documents$ chmod +x test
prometheus@Bartix:~/Documents$ ./test
Enter a number: 4

The Number 4 is not a prime

The Number 4 is a prime


Previously tested it with 27, which goes OK, but 4 is even so...



if(num>1 && (!(div<=num/2)))


Should be the condition. Now for a minor touch up:

#include<stdio.h>

int main()
{
int div;
int num;

printf("Enter a number: ");
scanf("%d", &num);

if(num>=2)
for(div=2; div<=num/2; div++)
if(num%div==0)
break;

if(num>1 && (!(div<=num/2)))
printf("\nThe Number %d is a prime\n", num);
else
printf("\nThe Number %d is not a prime\n", num);

return 0;
}


EDIT: The touch-up thing is ensuring that the program gives output in the rare (previously broken) cases. For instance, running the programatically-fixed version with input 0 wouldn't yield any output as no printf() call could be reached. So I restructured the code to make all non-primes fall into the else clause.
Thanks. I would also put your algorithm in C++ as well.

[Reiger]

Well your C++ original refuse to compile: gcc spits out more gibberish than I can cope with, given I don't know C++. (I can read some of the code based on my experience with other, similar, languages; but I can't mkae heads or tails from what the GCC says...)


/tmp/ccCcmLVO.o: In function `std::__verify_grouping(char const*, unsigned int, std::basic_string<char, std::char_traits<char>, std::allocator<char> > const&)':
prime.cc:(.text+0xe): undefined reference to `std::basic_string<char, std::char_traits<char>, std::allocator<char> >::size() const'
prime.cc:(.text+0x59): undefined reference to `std::basic_string<char, std::char_traits<char>, std::allocator<char> >::operator[](unsigned int) const'
prime.cc:(.text+0x97): undefined reference to `std::basic_string<char, std::char_traits<char>, std::allocator<char> >::operator[](unsigned int) const'
prime.cc:(.text+0xdf): undefined reference to `std::basic_string<char, std::char_traits<char>, std::allocator<char> >::operator[](unsigned int) const'
/tmp/ccCcmLVO.o: In function `__static_initialization_and_destruction_0(int, int)':
prime.cc:(.text+0x129): undefined reference to `std::ios_base::Init::Init()'
/tmp/ccCcmLVO.o: In function `__tcf_0':
prime.cc:(.text+0x176): undefined reference to `std::ios_base::Init::~Init()'
/tmp/ccCcmLVO.o: In function `main':
prime.cc:(.text+0x199): undefined reference to `std::cout'
prime.cc:(.text+0x19e): undefined reference to `std::basic_ostream<char, std::char_traits<char> >& std::operator<< <std::char_traits<char> >(std::basic_ostream<char, std::char_traits<char> >&, char const*)'
prime.cc:(.text+0x1ac): undefined reference to `std::cin'
prime.cc:(.text+0x1b1): undefined reference to `std::basic_istream<char, std::char_traits<char> >::operator>>(int&)'
prime.cc:(.text+0x1e5): undefined reference to `std::cout'
prime.cc:(.text+0x1ea): undefined reference to `std::basic_ostream<char, std::char_traits<char> >& std::operator<< <std::char_traits<char> >(std::basic_ostream<char, std::char_traits<char> >&, char const*)'
prime.cc:(.text+0x1f6): undefined reference to `std::basic_ostream<char, std::char_traits<char> >::operator<<(int)'
prime.cc:(.text+0x206): undefined reference to `std::basic_ostream<char, std::char_traits<char> >& std::operator<< <std::char_traits<char> >(std::basic_ostream<char, std::char_traits<char> >&, char const*)'
prime.cc:(.text+0x248): undefined reference to `std::cout'
prime.cc:(.text+0x24d): undefined reference to `std::basic_ostream<char, std::char_traits<char> >& std::operator<< <std::char_traits<char> >(std::basic_ostream<char, std::char_traits<char> >&, char const*)'
prime.cc:(.text+0x259): undefined reference to `std::basic_ostream<char, std::char_traits<char> >::operator<<(int)'
prime.cc:(.text+0x269): undefined reference to `std::basic_ostream<char, std::char_traits<char> >& std::operator<< <std::char_traits<char> >(std::basic_ostream<char, std::char_traits<char> >&, char const*)'
/tmp/ccCcmLVO.o:(.eh_frame+0x11): undefined reference to `__gxx_personality_v0'
collect2: ld returned 1 exit status

[Canis familiaris]

Well your C++ original refuse to compile: gcc spits out more gibberish than I can cope with, given I don't know C++. (I can read some of the code based on my experience with other, similar, languages; but I can't mkae heads or tails from what the GCC says...)


/tmp/ccCcmLVO.o: In function `std::__verify_grouping(char const*, unsigned int, std::basic_string<char, std::char_traits<char>, std::allocator<char> > const&)':
prime.cc:(.text+0xe): undefined reference to `std::basic_string<char, std::char_traits<char>, std::allocator<char> >::size() const'
prime.cc:(.text+0x59): undefined reference to `std::basic_string<char, std::char_traits<char>, std::allocator<char> >::operator[](unsigned int) const'
prime.cc:(.text+0x97): undefined reference to `std::basic_string<char, std::char_traits<char>, std::allocator<char> >::operator[](unsigned int) const'
prime.cc:(.text+0xdf): undefined reference to `std::basic_string<char, std::char_traits<char>, std::allocator<char> >::operator[](unsigned int) const'
/tmp/ccCcmLVO.o: In function `__static_initialization_and_destruction_0(int, int)':
prime.cc:(.text+0x129): undefined reference to `std::ios_base::Init::Init()'
/tmp/ccCcmLVO.o: In function `__tcf_0':
prime.cc:(.text+0x176): undefined reference to `std::ios_base::Init::~Init()'
/tmp/ccCcmLVO.o: In function `main':
prime.cc:(.text+0x199): undefined reference to `std::cout'
prime.cc:(.text+0x19e): undefined reference to `std::basic_ostream<char, std::char_traits<char> >& std::operator<< <std::char_traits<char> >(std::basic_ostream<char, std::char_traits<char> >&, char const*)'
prime.cc:(.text+0x1ac): undefined reference to `std::cin'
prime.cc:(.text+0x1b1): undefined reference to `std::basic_istream<char, std::char_traits<char> >::operator>>(int&)'
prime.cc:(.text+0x1e5): undefined reference to `std::cout'
prime.cc:(.text+0x1ea): undefined reference to `std::basic_ostream<char, std::char_traits<char> >& std::operator<< <std::char_traits<char> >(std::basic_ostream<char, std::char_traits<char> >&, char const*)'
prime.cc:(.text+0x1f6): undefined reference to `std::basic_ostream<char, std::char_traits<char> >::operator<<(int)'
prime.cc:(.text+0x206): undefined reference to `std::basic_ostream<char, std::char_traits<char> >& std::operator<< <std::char_traits<char> >(std::basic_ostream<char, std::char_traits<char> >&, char const*)'
prime.cc:(.text+0x248): undefined reference to `std::cout'
prime.cc:(.text+0x24d): undefined reference to `std::basic_ostream<char, std::char_traits<char> >& std::operator<< <std::char_traits<char> >(std::basic_ostream<char, std::char_traits<char> >&, char const*)'
prime.cc:(.text+0x259): undefined reference to `std::basic_ostream<char, std::char_traits<char> >::operator<<(int)'
prime.cc:(.text+0x269): undefined reference to `std::basic_ostream<char, std::char_traits<char> >& std::operator<< <std::char_traits<char> >(std::basic_ostream<char, std::char_traits<char> >&, char const*)'
/tmp/ccCcmLVO.o:(.eh_frame+0x11): undefined reference to `__gxx_personality_v0'
collect2: ld returned 1 exit status

Use g++ to compile the C++ code. g++ is actually gcc called with special C++ libraries.


g++ filename -o program

[Zugzwang]

Well your C++ original refuse to compile: gcc spits out more gibberish than I can cope with, given I don't know C++. (I can read some of the code based on my experience with other, similar, languages; but I can't mkae heads or tails from what the GCC says...)


That's not surprising! The command to compile C++ code is "g++".

[Reiger]

Here you are:


#include<iostream>
using namespace std;

int main()
{
int div;
int num;

cout<<"Enter a number: ";
cin>>num;

if(num>=2)
for(div=2; div<=num/2; div++)
if(num%div==0)
break;

if(num>1 && (!(div<=num/2)))
cout<<"The number "<<num<<" is a prime\n";
else
cout<<"The number "<<num<<" is not a prime\n";

return 0;
}

[snova]

Well, it's no Sieve of Atkins, but it'll have to do. Compile and run with the number to test as it's argument. It'll give correct results for everything except 1 and negative numbers (you get segfaults for those). The return value is whether it's a prime or not. Keep in mind it's not shell boolean.


main(int c,char**v){unsigned int s=atoll(v[1])+1,p=0,m=3;char*a
=malloc(s);for(;p<s;p++)a[p]=1;while(m*m<s){p=m*m;while(p<s){a[p
]=0;p+=m;}m+=2;while(!a[m]&&m*m<s)m+=2;}return s-1%2?a[s-1]:0;}

It's not nearly as good as my last piece. :(

[nvteighen]

Scheme

The trick here is that we can create a truly infinite stream of primes by just giving the rules for the Sieve of Eratosthenes from an infinite stream of integers generated by the rules of Induction Theory.

And then, we just check whether the input is part of the stream or not. When found, it returns "true" (#t), but when the next prime number is bigger than the test case it's obvious that the number is not prime, so it returns #f. If none of both conditions is met, the program continues by demanding more information from the primes stream.

These are the kind of nice things you can do in this language.


;; A Primality-checker in Scheme

;; We create a predicate that checks a number for primality. To use it, start
;; some Scheme interpreter, load this module and type (prime? <number>). If
;; true, it returns #t and, if false, #f; so, you can use this in a conditional
;; as any built-in predicate.
(define (prime? number)

;; Creates an infinite stream of integers starting from n
(define (int-stream-from n)
(cons-stream n
(int-stream-from (+ n 1))))

;; Checks if y is a divisor of x.
(define (div? x y)
(= 0 (modulo x y)))

;; Creates an infinite stream of primes, using the Sieve of Eratosthenes.
(define (eratosthenes row)
(cons-stream (stream-car row)
(eratosthenes
(stream-filter (lambda (x)
(not (div? x
(stream-car row))))
(stream-cdr row)))))

;; And after having defined the auxiliary local procedures, we now code the
;; body. It's just a classic, trivial Scheme-ish tail recursion.
(let loop ((primes (eratosthenes (int-stream-from 2))))
(cond ((< number (stream-car primes))
#f)
((= number (stream-car primes))
#t)
(else (loop (stream-cdr primes))))))

[dribeas]

Ideally, you would only need to do the division for prime numbers below the square root of the number, but I can't work out a way of doing that that's actually less expensive than doing it your way.

While dividing only by prime numbers is hard you can reduce computation time by half by just checking odd numbers (that is, change the loop iteration from i++ to i+=2). Clearly, if the number were divisible by an even number it would surely be divisible by 2, which is the first test.

[jimi_hendrix]

using System;

namespace IsPrime
{
class Program
{
static void Main()
{
//prompt user for input and read it
Console.WriteLine("please enter a number to check:");
int check = Convert.ToInt32(Console.ReadLine());

//check for the not possible primes
if (check < 2)
{
Console.WriteLine("the number you entered can not be prime");
Console.WriteLine("press any key to exit");
Console.ReadKey(); //pauses the program for the user to read
return; //exits the program
}

//begin for loop to check for the prime
for (int i = 2; i < check; i++)
{

if ((check % i) == 0) //tells user if number is not prime
{
Console.WriteLine("the number is not prime");
Console.WriteLine("press any key to exit...");
Console.ReadKey();
return;
}
}

//tells user number is prime
Console.WriteLine("the number is prime");
Console.WriteLine("press any key to exit");
Console.ReadKey();
}
}
}

[Reiger]

Scheme

The trick here is that we can create a truly infinite stream of primes by just giving the rules for the Sieve of Eratosthenes from an infinite stream of integers generated by the rules of Induction Theory.

And then, we just check whether the input is part of the stream or not. When found, it returns "true" (#t), but when the next prime number is bigger than the test case it's obvious that the number is not prime, so it returns #f. If none of both conditions is met, the program continues by demanding more information from the primes stream.

These are the kind of nice things you can do in this language.


You do *exactly* the same in Lisp as I did in Haskell before I optimised (to reduce the complexity with a factor O(sqrt(n)) ):


isPrime q = (q==) $ last $ primes [2..q] {- Generate a list of integers, remove the non-prime numbers, grab the last item in the result list, return if that item is equal to the input (prime!) or not (not-prime!). -}

[jimi_hendrix]

Module Module1
Dim prime As Integer
Dim isPrime As Boolean = False
Sub Main()
Console.WriteLine("enter an integer to check")
prime = Console.ReadLine()

If prime < 2 Then
Console.WriteLine("the number is not possibly prime")
Console.WriteLine("press any key to exit")
Console.ReadKey()
System.Environment.Exit(0)
End If


For index As Integer = 2 To (prime - 1)

If (prime Mod index) = 0 Then
isPrime = False
End If
Next


If isPrime <> True Then
Console.WriteLine("the number is prime")
Console.WriteLine("press any key to exit")
Console.ReadKey()

Else
Console.WriteLine("the number is not prime")
Console.WriteLine("press any key to exit")
Console.ReadKey()
End If


End Sub

End Module

[dribeas]

//check for the not possible primes
if (check == 0 | check == 1 | check == 2)
{
Console.WriteLine("the number you entered can not be prime");


:) Small mistake: 2 is definitely a prime number. The same goes with 1, even if I think mathematicians consider it a non-proper prime... anyone cares to clear this point?

Oh, and you should check for negative values (as you did in your VB version)

[pp.]

Small mistake: 2 is definitely a prime number. The same goes with 1, even if I think mathematicians consider it a non-proper prime... anyone cares to clear this point?

In that case, every positive integer is a non-proper prime.

A positive odd integer is prime if it can be divided by 1 and itself only.

A positive even integer is prime if it is equal to 2.

[Idefix82]

1 is not a prime!!!
If it was then there would be no unique factorisation into prime factors since 2= 1*2.
"Prime number" is a mathematical term so what the mathematicians consider it to mean is what it means :)

Edit: just to reiterate, there is no such term as "proper prime" and "improper prime".

[jimi_hendrix]

In that case, every positive integer is a non-proper prime.

A positive odd integer is prime if it can be divided by 1 and itself only.

A positive even integer is prime if it is equal to 2.


:) Small mistake: 2 is definitely a prime number. The same goes with 1, even if I think mathematicians consider it a non-proper prime... anyone cares to clear this point?

Oh, and you should check for negative values (as you did in your VB version)


1 is not a prime!!!
If it was then there would be no unique factorisation into prime factors since 2= 1*2.
"Prime number" is a mathematical term so what the mathematicians consider it to mean is what it means :)

Edit: just to reiterate, there is no such term as "proper prime" and "improper prime".

see what happens when you post late at night...fixing it now

[jespdj]

The number 1 is not a prime number.

See Prime number (http://en.wikipedia.org/wiki/Prime_number) on Wikipedia, it also has some information on why 1 is not a prime number. Basically, if 1 would be a prime number, the fundamental theorem of arithmetic (http://en.wikipedia.org/wiki/Fundamental_theorem_of_arithmetic) would not be valid.

[mosty friedman]

done in Java

import java.util.Scanner;
public class PrimeTest
{
public static void isPrime( int n )
{
boolean prime = true;
if( n < 2 )
prime = false;

for( int i = 2; i < n; i++ )
{
if( n % i == 0 )
{
prime = false;
break;
}
}
if( prime )
System.out.printf( "%d %s\n", n, "is a prime number" );
else
System.out.printf( "%d %s\n", n, "is not a prime number" );
}

public static void main( String[]args )
{
Scanner sc = new Scanner( System.in );
System.out.println( "enter a number to check if its prime or not");
int num = sc.nextInt();
isPrime( num );
}

}

any tips or any feedback are appreciated :)

[geirha]

any tips, hints or any feedback is appreciated :)

Instead of checking for 1 or 0, check for less than 2 instead, that way you'll handle negative numbers as well. The task does not mention what to do with negative numbers, so you can treat them as not primes.

[mosty friedman]

Instead of checking for 1 or 0, check for less than 2 instead, that way you'll handle negative numbers as well. The task does not mention what to do with negative numbers, so you can treat them as not primes.
thanks for that tip..that was a useful one..never payed attention to that

[nvteighen]

You do *exactly* the same in Lisp as I did in Haskell before I optimised (to reduce the complexity with a factor O(sqrt(n)) ):


isPrime q = (q==) $ last $ primes [2..q] {- Generate a list of integers, remove the non-prime numbers, grab the last item in the result list, return if that item is equal to the input (prime!) or not (not-prime!). -}


Well, I never said Scheme is the only nice way to do it... Actually, using an infinite stream is an advantage you get in functional programming... and it's just so much nicer than imperative solutions...

By the way, my code is not exactly the same as your Haskell (as far as I could understand it...), as you developed an application in Haskell, but I instead wrote a procedure on Scheme that extends the language and therefore, to use it, you start the interpreter (The Lisp Machine of our days...), load the module (but a simple shell script would ease that to the user) and type (prime? ...) when you need it.

The "classic" development style on Scheme (don't know what about other Lisp dialects) is just that: I extend the language to my needs, load it into the interpreter and then let the user type in the commands he needs... and if he/she needs to extend my extensions, he/she'll do exactly the same, etc. etc. etc. and all extensions will be just Lisp objects, which is the difference why you can do this in Python, Perl or other interpreted languages: yeah, you can extend the language, start the interpreter loading the module (and, e.g. using the -i flag in Python to stay in interactive mode), but those extensions won't be embedded into Python itself, but just implemented in Python.

Yeah, it's a bit weird and probably not "usable" for the end-user, who expects an interface (better if GUI), not a Scheme interpreter with some module loaded and then start playing with it.

[jimi_hendrix]

FORTRAN 77 (with goto instead of subprograms (functions in most other languages))


program prime
integer tocheck, i, ret

write (*,*) 'what is the number to check?'
read (*,*) tocheck

if (tocheck .lt. 2) then
write (*,*) 'the number prime'
goto 2
endif
do 1 i = 1, (tocheck - 1)
ret = mod(tocheck,i)
if (ret .eq. 0) then
write (*,*) 'the number prime'
goto 2
endif
1 continue

2 stop
end

you should retype this code in all caps for tradition

[pp.]

FORTRAN 77 (with goto instead of subprograms (functions in most other languages))

When and where does it tell that a number is prime?
Why does it say that a number is prime whenever it is not?

Oh, and goto does not do anything resembling a function or a procedure.

[jimi_hendrix]

i really have to stop posting late at night...ill edit it later...and i never said goto was a funtion...i said subprograms were

[Reiger]

Well, I never said Scheme is the only nice way to do it... Actually, using an infinite stream is an advantage you get in functional programming... and it's just so much nicer than imperative solutions...

It's mostly the benefit of lazy evaluation/programming... the inifite stream gets never fully evaluated, only as far as is needed...



By the way, my code is not exactly the same as your Haskell (as far as I could understand it...), as you developed an application in Haskell, but I instead wrote a procedure on Scheme that extends the language and therefore, to use it, you start the interpreter (The Lisp Machine of our days...), load the module (but a simple shell script would ease that to the user) and type (prime? ...) when you need it.

Well no not really, load it in an interpreter and you can use these as 'native' built-in functions. For instance, if you load this module in the GHCI you would be able to filter out all relative primes in the sequence [4,5,6,7,8,9,10] by typing primes [4,5,6,7,8,9,10]. So wheter or not it's the same as Lisp I'm not sure (not familiar with Lisp), but it would appear that the effect to the user is pretty much the same.

[lisati]

FORTRAN 77 (with goto instead of subprograms (functions in most other languages))


program prime
integer tocheck, i, ret

write (*,*) 'what is the number to check?'
read (*,*) tocheck

if (tocheck .lt. 2) then
write (*,*) 'the number prime'
goto 2
endif
do 1 i = 1, (tocheck - 1)
ret = mod(tocheck,i)
if (ret .eq. 0) then
write (*,*) 'the number prime'
goto 2
endif
1 continue

2 stop
end

you should retype this code in all caps for tradition
I'd suggest starting the DO loop at 2 - unless I'm mistaken, "any positive integer" modulus 1 would equal zero.

[nvteighen]

It's mostly the benefit of lazy evaluation/programming... the inifite stream gets never fully evaluated, only as far as is needed...

Yeah, you're right. But are there imperative programming languages with lazy evaluation?


Well no not really, load it in an interpreter and you can use these as 'native' built-in functions. For instance, if you load this module in the GHCI you would be able to filter out all relative primes in the sequence [4,5,6,7,8,9,10] by typing primes [4,5,6,7,8,9,10]. So wheter or not it's the same as Lisp I'm not sure (not familiar with Lisp), but it would appear that the effect to the user is pretty much the same.

You can do that with any interpreted language that has an interactive shell. The difference in Lisp is that there's absolutely no distinction between built-in procedures and the ones you created... there's no differnce even with syntactic keywords because the syntax is always the same for everything:



(procedure datum)


By that, any procedure you create becomes part of the language, not just something implemented in the language. For example, there's no language (as far as I know) that treats your created procedures exactly the same as the + operator, except Lisp, where (+ 2 3) has the same syntax than creating a procedure called 'add' (add 2 3)... So, the boundary between "operators" and "procedures" is destroyed... This, plus, the "code <=> data" (homoiconicity) principle makes Lisp more than a language, but a framework to create languages and therefore so different to anything else (hey, can you take the second element of a procedure...? In Lisp you can, as any procedure is a list, so it has a second element!).

As you already know a functional programming language, I really recommend you learn some sort of Lisp to see it on your own.

[pp.]

... are there imperative programming languages with lazy evaluation?

Yes, but they call it something else. Classical example: short-circuited compound conditions. In "A and B", "B" will be executed only if "A" evaluates to true.


there's no language (as far as I know) that treats your created procedures exactly the same as the + operator, except Lisp, where (+ 2 3) has the same syntax than creating a procedure called 'add' (add 2 3)

Smalltalk does that, too. Operators are just funny selectors.

[Zugzwang]

If I remember correctly, lately (less than 8 years ago) there was discovered some prime number testing algorithm with a running time polynomial in the length of the prime number given (and without randomisation). That one would be quite nice to see here! Does anyone have more information (Google doesn't reveal much)?

[Bichromat]

If I remember correctly, lately (less than 8 years ago) there was discovered some prime number testing algorithm with a running time polynomial in the length of the prime number given (and without randomisation). That one would be quite nice to see here! Does anyone have more information (Google doesn't reveal much)?

Is this what you're talking about: http://mathworld.wolfram.com/AKSPrimalityTest.html ?
It is asymptotically faster than other methods, but I think it is too slow and cumbersome to be useful on small numbers. The best algorithm available is the Elliptic curve test.
For small enough numbers (less than 15 digits), a probabilistic test like Rabin-Miller is sufficient (if you take enough bases).
Even for larger numbers, the probability of a false positive is very small.

[Nemooo]

My solution in Arc (http://arclanguage.com/):


; Returns t if the number is a prime and nil otherwise.
; Run with (is-prime x)

(def is-prime (x)
(if (is x 2) t
(or (< x 2) (is (mod x 2) 0)) nil
(check-prime x)))

(def check-prime (x)
(with (return t i 3 limit (sqrt x))
(while (<= i limit)
(when (is (mod x i) 0)
(= return nil)
(= limit 0))
(zap [+ _ 2] i))
return))


EDIT: This is in my opinion a lot more elegant and more efficient. Has anyone else given Arc a try?

[achelis]

done in Java

import java.util.Scanner;
public class PrimeTest
{
public static void isPrime( int n )
{
boolean prime = true;
if( n < 2 )
prime = false;

for( int i = 2; i < n; i++ )
{
if( n % i == 0 )
{
prime = false;
break;
}
}
if( prime )
System.out.printf( "%d %s\n", n, "is a prime number" );
else
System.out.printf( "%d %s\n", n, "is not a prime number" );
}

public static void main( String[]args )
{
Scanner sc = new Scanner( System.in );
System.out.println( "enter a number to check if its prime or not");
int num = sc.nextInt();
isPrime( num );
}

}

any tips or any feedback are appreciated :)

My 2 cents: I would change the isPrime method to return a boolean indicating whether the number given is a boolean or not. Imo it's not nice to have a function doing both calculation/modelling and output/view.
The second thing is that, as has been mentioned before, you only need to check all uneven numbers up to the square root of n.
I took the liberty to modify your code to this:

import java.util.Scanner;
public class PrimeTest
{
public static boolean isPrime( int n ) {
if( n < 2 || (0x01 & n) == 0)
return false;
if(n == 2)
return true;

int h = (int) Math.sqrt(n);
for( int i = 3; i <= h; i += 2 ) {
if( n % i == 0 ) {
return false;
}
}
return true;
}

public static void main( String[]args ) {
Scanner sc = new Scanner( System.in );
System.out.println( "enter a number to check if its prime or not");
int n = sc.nextInt();
if (isPrime( n ))
System.out.println(n + " is a prime.");
else
System.out.println(n + " is not a prime.");
}
}

Alternatively the print-out could be written as:


System.out.println(n + " is " + (isPrime(n) ? "" : "not ") + "a prime.");

[Barrucadu]

Common Lisp:


(defun isprime (x)
(if (< x 2)
(return-from isprime nil)
(dotimes (i (+ (ceiling (sqrt x)) 1))
(if (> i 1)
(if (< i x)
(if (equal (mod x i) 0)
(return-from isprime nil))))))
(return-from isprime t))

[Lux Perpetua]

If I remember correctly, lately (less than 8 years ago) there was discovered some prime number testing algorithm with a running time polynomial in the length of the prime number given (and without randomisation). That one would be quite nice to see here! Does anyone have more information (Google doesn't reveal much)?Here you go. :-) For your amusement:
/* AKS Primality Algorithm.
*
* Described here:
*
* http://www.cse.iitk.ac.in/~manindra/algebra/primality_v6.pdf
*
* Actually, the algorithm implemented here is considerably less
* efficient than the one described in the paper due to my naive
* polynomial squaring algorithm. Nevertheless, it is still a
* polynomial-time primality testing algorithm.
*/


#include <iostream>
#include <sstream>

/* This is the default for integers expected to be of size comparable to
* the number whose primality is being checked. */
typedef uint32_t reg_int;

/* This is used as necessary to prevent overflow. */
typedef uint64_t big_int;

/* Compute n^b. */
reg_int power(reg_int n, unsigned int b) {
if (b == 0)
return 1;

reg_int m(power(n, b>>1));
m *= m;

if (b & 1)
m *= n;

return m;
}

/* Compute floor(n^(1/b)). This is not the cleverest algorithm, but it's
* acceptably fast, and it isn't the bottleneck of the program, so
* there's no reason to optimize it now.
*/
reg_int root(reg_int n, unsigned int b) {
if (n < 1)
return 0;

reg_int m(root(n >> b, b)<<1);
reg_int k(m + 1);

if (power(k, b) <= n)
return k;
else
return m;
}

/* Compute the Euler totient function of n (number of positive integers
* up to n relatively prime to n). The running time is exponential in
* the length of n, but that's okay, since the number it will be used on
* is small compared to the number whose primality is being
* checked. It's not the bottleneck, so there's no reason to worry about
* it.
*/
unsigned int phi(unsigned int n) {
if (n == 1)
return 1;

unsigned int p(2);

while (true) {
if (n % p == 0) {
n /= p;
unsigned int q(1);
unsigned int m(n);

while (m % p == 0) {
m /= p;
q *= p;
}
return (p - 1)*q*phi(m);
}
p += 1;
}
}

/* Usage: instantiate this class on a positive integer and either cast
* it to a string (for informative output) or a bool (for a simple
* true/false determination of the primality of the integer).
*/
class primality_check {
unsigned int r;
reg_int n;
unsigned int lgn; // log_2(n)
bool val;

/* These are work buffers used by the polynomial arithmetic
* subroutines. They represent polynomials mod x^r - 1. Note: all
* polynomial arithmetic is mod (x^r - 1, n). The outines operate on
* Accum_A (as source and destination) and use Accum_B for scratch
* work or to store results as needed.
*/

reg_int * Accum_A;
reg_int * Accum_B;

std::ostringstream messages;

void clear(reg_int *P) {
for (unsigned int k = 0; k < r; ++k) {
P[k] = 0;
}
}

void swap() {
reg_int *D = Accum_A;
Accum_A = Accum_B;
Accum_B = D;
}

/* Multiply Accum_A by (x + a). */
void mul_a(unsigned int a) {
reg_int last(Accum_A[r-1]);

for (unsigned int k = r-1; k > 0; --k) {
big_int t(Accum_A[k]);
t *= a;
t += Accum_A[k-1];
t %= n;

Accum_A[k] = t;
}
big_int t(Accum_A[0]);
t *= a;
t += last;
t %= n;

Accum_A[0] = t;
}

/* Square Accum_A. This is the bottleneck of the program and
* basically cripples this implementation. :-( There are faster ways
* to square a polynomial, but they're much more complicated.
*/
void sqr() {
swap();
clear(Accum_A);

for (unsigned int k = 0; k < r; ++k) {
unsigned int k2 = (k + k) % r;

big_int t(Accum_B[k]);
t *= t;
t += Accum_A[k2];
t %= n;

Accum_A[k2] = t;

for (unsigned int j = k + 1; j < r; ++j) {
unsigned int i = (j + k) % r;

big_int t(Accum_B[k]);
t *= Accum_B[j];
t += t;
t += Accum_A;
t %= n;

Accum_A[i] = t;
}
}
}

[i]/* Compute (x + a)^n and put result in Accum_A. */
void pow(unsigned int a) {
clear(Accum_A);
Accum_A[0] = a;
Accum_A[1] = 1;

for (unsigned int k = lgn - 1; k > 0; --k) {
sqr();

if ((n >> (k-1)) & 1 == 1) {
mul_a(a);
}
}
}

/* Determine if (x + a)^n == x^n + a. */
bool test(unsigned int a) {
pow(a);

if (Accum_A[0] != a) {
return false;
}

for (unsigned int k = 1; k < n % r; ++k) {
if (Accum_A[k] != 0) {
return false;
}
}

if (Accum_A[n % r] != 1) {
return false;
}

for (unsigned int k = (n % r) + 1; k < r; ++k) {
if (Accum_A[k] != 0) {
return false;
}
}

return true;
}

public:
primality_check(reg_int p);

operator bool () const {
return val;
}

operator std::string () const {
return messages.str();
}

~primality_check() {
delete [] Accum_A;
delete [] Accum_B;
}
};

primality_check::primality_check(reg_int p)
: n(p), Accum_A(0), Accum_B(0)
{
lgn = 0;

reg_int m(n);

while (m != 0) {
m >>= 1;
++lgn;
}

// 1. Check if n is a perfect power
m = n;
unsigned int b = 1;
while (m > 1) {
++b;
m = root(n, b);
if (power(m, b) == n) {
val = false;
messages << "Composite! ("
<< n << " = " << m << "^" << b << ")";
return;
}
}

// 2. Determine r
unsigned int target(lgn*lgn);

unsigned int order(0);
r = 1;

while (order < target) {
++r;
order = 1;
unsigned int q(n % r);

while (q != 1) {
if (order >= target) {
break;
}

q = (q * n) % r;
++order;
}
}

Accum_A = new reg_int[r];
Accum_B = new reg_int[r];

// 3. Check if n has any proper factors up to r
for (unsigned int k = 2; k <= r; ++k) {
if (n % k == 0) {
if (k == n) {
// 4. We actually just proved n is prime
val = true;
messages << "Prime! (checked exhaustively)";
return;
} else {
val = false;
messages << "Composite! (divisible by " << k << ")";
return;
}
}
}

// 5. Polynomial test (the heart of the algorithm)

unsigned int limit((root(phi(r), 2) + 1)*lgn);

for (unsigned int a = 1; a <= limit; ++a) {
if (!test(a)) {
val = false;
messages << "Composite! (failed polynomial test with a = "
<< a << ", r = " << r << ")";
return;
}
}

// 6.
val = true;
messages << "Prime! (passed all tests)";
}

std::ostream & operator << (std::ostream & os, const primality_check & PC) {
os << static_cast<std::string>(PC);
return os;
}

int main(int argc, char **argv) {
using namespace std;

if (argc < 2) {
cerr << "Usage: " << argv[0] << " number_to_test" << endl;
return 1;
}

istringstream is(argv[1]);

reg_int n;

if (!(is >> n)) {
cerr << "Usage: " << argv[0] << " number_to_test" << endl;
return 1;
}

primality_check PC(n);

cout << PC << endl;

return 0;
}
To compile:
g++ -ansi -Wall -pedantic -O3 aks_uint.cppSee the comments for specific details about the implementation. It doesn't achieve the asymptotic running time advertised in the paper because my polynomial squaring is very suboptimal. However, it's technically still polynomial-time. Typical results on my computer:
%>time a.out 1299721
Prime! (passed all tests)

real 1m42.026s
user 1m32.454s
sys 0m0.040sThis program can be ported painlessly to gmpxx. In fact, I've already done it, but it's probably not very useful, since this version is slow enough already, and the gmpxx version is more than ten times as slow.

[jimi_hendrix]

my first perl script...



#!/usr/bin/perl

print "what is the number you would like to check?\n";
my $check = <>; #<> is short for <STDIN>, both would work here

#begin checking
for (my $i = 2; $i < $check; $i++)
{
if ($check % $i == 0)
{
print "the number is not prime\n";
exit;
}
}

print "the number is prime\n";



any comments would be great

[Reiger]

And what would happen if the number entered was smaller than 2? Hint: see the C & C++ entries.

[Reiger]

import java.util.Scanner;
public class PrimeTest
{
public static boolean isPrime( int n ) {
if( n < 2 || (0x01 & n) == 0)
return false;
if(n == 2)
return true;

int h = (int) Math.sqrt(n);
for( int i = 3; i <= h; i += 2 ) {
if( n % i == 0 ) {
return false;
}
}
return true;
}

public static void main( String[]args ) {
Scanner sc = new Scanner( System.in );
System.out.println( "enter a number to check if its prime or not");
int n = sc.nextInt();
if (isPrime( n ))
System.out.println(n + " is a prime.");
else
System.out.println(n + " is not a prime.");
}
}


This code will fail to recognize 2 as a prime, but that can be solved readily by changing order of a few lines to:


if(n == 2)
return true;

if( n < 2 || (0x01 & n) == 0)
return false

[Lux Perpetua]

I've revamped my AKS implementation using gmpxx and the polynomial multiplication hack explained here:

http://www.apple.com/acg/pdf/aks3.pdf

Now it's actually faster than my native integer implementation. To wit: the "hard" operation, polynomial squaring, can piggyback on big integer arithmetic. Ironically, the code is simpler and it runs faster, since most of the real work is pushed into the GMP library.
/* AKS Primality Algorithm.
*
* Described here:
*
* http://www.cse.iitk.ac.in/~manindra/algebra/primality_v6.pdf
*
* The crucial part of the algorithm, which requires verifying a long
* list of polynomial identities, is implemented using a useful hack
* explained here:
*
* http://www.apple.com/acg/pdf/aks3.pdf
*/

#include <iostream>
#include <sstream>
#include <gmpxx.h>

/* Compute n^b. */
mpz_class power(const mpz_class & n, unsigned int b) {
if (b == 0)
return 1;

mpz_class m(power(n, b>>1));
m *= m;

if (b & 1)
m *= n;

return m;
}

/* Compute floor(n^(1/b)). This is not the cleverest algorithm, but it's
* acceptably fast and correct.
*/
mpz_class root(const mpz_class & n, unsigned int b) {
if (n < 1)
return 0;

mpz_class m(root(n >> b, b)<<1);
mpz_class k(m + 1);

if (power(k, b) <= n)
return k;
else
return m;
}

/* Compute the Euler totient function of n (number of positive integers
* up to n relatively prime to n). The running time is exponential in
* the length of n, but that's okay, since the number it will be used on
* is small compared to the number whose primality is being
* checked. It's not the bottleneck, so there's no reason to worry about
* it.
*/
unsigned int phi(unsigned int n) {
if (n == 1)
return 1;

unsigned int p(2);

while (true) {
if (n % p == 0) {
n /= p;
unsigned int q(1);
unsigned int m(n);

while (m % p == 0) {
m /= p;
q *= p;
}
return (p - 1)*q*phi(m);
}
p += 1;
}
}

/* Find the number of bits of n ( = floor(log_2(n + 1))). */
unsigned int lg(const mpz_class & n) {
mpz_class m(n);
unsigned int k = 0;

while (m > 0) {
m >>= 1;
++k;
}

return k;
}

/* Usage: instantiate this class on a positive integer and either cast
* it to a string (for informative output) or a bool (for a simple
* true/false determination of the primality of the integer).
*/

class primality_check {
unsigned int r;
mpz_class n;
unsigned int lgn; // log_2(n)
bool val;

mpz_class accum;

unsigned int cell_size;
mpz_class cell_mask;
mpz_class full_mask;

std::ostringstream messages;

void dump(const mpz_class & P) {
for (unsigned int k = 0; k < r; ++k) {
mpz_class coeff(P & (cell_mask << (cell_size * k)));
coeff >>= cell_size * k;
std::cout << coeff << ' ';
}
std::cout << std::endl;
}

/* Reduce accum mod (x^r - 1) after a multiplication */
void reduce_poly() {
accum += (accum >> (cell_size * r));
accum &= full_mask;
}

/* Reduce accum mod (n) after arithmetic */
void reduce_coeffs() {
mpz_class temp(0);
for (unsigned int k = 0; k < r; ++k) {
mpz_class coeff(accum & (cell_mask << (cell_size * k)));
coeff >>= cell_size * k;
coeff %= n;

temp ^= (coeff << (cell_size * k));
}
//dump(temp);
accum = temp;
}

/* Compute (x + a)^n and put result in accum. */
void pow(const mpz_class & a) {
accum = 1;
accum <<= cell_size;
accum += a;

for (unsigned int k = lgn - 1; k > 0; --k) {
accum *= accum;
reduce_poly();

if ((mpz_class((n >> (k-1))).get_ui() & 1) == 1) {
accum = (accum * a) + (accum << cell_size);
reduce_poly();
}
reduce_coeffs();
}
}

/* Determine if (x + a)^n == x^n + a. */
bool test(const mpz_class & a) {
pow(a);

unsigned int idx = mpz_class(n % r).get_ui();
mpz_class target(1);
target <<= (cell_size * idx);
target += a;

return accum == target;
}

public:
primality_check(const mpz_class & p);

operator bool () const {
return val;
}

operator std::string () const {
return messages.str();
}
};

primality_check::primality_check(const mpz_class & p)
: n(p), lgn(lg(n))
{
if (n == 0) {
val = false;
messages << "Zero!";
return;
}

if (n == 1) {
val = false;
messages << "Unit!";
return;
}

// 1. Check if n is a perfect power
mpz_class m(n);
unsigned int b = 1;
while (m > 1) {
++b;
m = root(n, b);
if (power(m, b) == n) {
val = false;
messages << "Composite! ("
<< n << " = " << m << "^" << b << ")";
return;
}
}

// 2. Determine r
mpz_class target(lgn*lgn);

mpz_class order(0);
r = 1;

while (order < target) {
++r;
order = 1;
unsigned int q = mpz_class(n % r).get_ui();

while (q != 1) {
if (order >= target) {
break;
}

q = mpz_class((q * n) % r).get_ui();
++order;
}
}

// 3. Check if n has any proper factors up to r
for (unsigned int k = 2; k <= r; ++k) {
if (n % k == 0) {
if (k == n) {
// 4. We actually just proved n is prime
val = true;
messages << "Prime! (checked exhaustively)";
return;
} else {
val = false;
messages << "Composite! (divisible by " << k << ")";
return;
}
}
}

// 5. Polynomial test (the heart of the algorithm)

mpz_class limit((root(phi(r), 2) + 1)*lgn);

/* This should give us enough padding to do an operation of type
accum = accum^2*(x + a) without reducing mod n until the end */
cell_size = lgn + lgn + lg(r) + lg(limit + 1);

cell_mask = 1;
cell_mask <<= cell_size;
--cell_mask;

full_mask = 1;
full_mask <<= r*cell_size;
--full_mask;

for (mpz_class a = 1; a <= limit; ++a) {
if (!test(a)) {
val = false;
messages << "Composite! (failed polynomial test with a = "
<< a << ", r = " << r << ")";
return;
}
}

// 6.
val = true;
messages << "Prime! (passed all tests)";
}

std::ostream & operator << (std::ostream & os, const primality_check & PC) {
os << static_cast<std::string>(PC);
return os;
}

int main(int argc, char **argv) {
using namespace std;

if (argc < 2) {
cerr << "Usage: " << argv[0] << " number_to_test" << endl;
return 1;
}

istringstream is(argv[1]);

mpz_class n;

if (!(is >> n)) {
cerr << "Usage: " << argv[0] << " number_to_test" << endl;
return 1;
}

primality_check PC(n);
cout << PC << endl;

return 0;
}
To compile:
g++ -ansi -Wall -pedantic -lgmpxx -lgmp -O3 aks_gmp.cpp -o aks_gmpYou will need libgmpxx. Typical results on my computer:
%> time aks_gmp 15485867
Prime! (passed all tests)

real 1m37.072s
user 1m36.570s
sys 0m0.020s
%> time aks_gmp 25775050868797
Composite! (failed polynomial test with a = 1, r = 2027)

real 0m5.405s
user 0m5.376s
sys 0m0.008s
(Note that 25775050868797 = 7368791*3497867, a product of two primes.)

[uljanow]

A slightly modified java version which uses miller-rabin-test

import java.util.*;

public class PrimeTest {
private static long modExp(int b, int e, int m) {
long c = 1;
for (int i = 0; i < e; i++)
c = (b*c) % m;
return c;
}
public static boolean isPrime(int p, int k) {
if (p < 2 || k < 1) return false;
Random rnd = new Random(System.currentTimeMillis());
for (int i = 0; i < k; i++)
if (modExp(1 + rnd.nextInt(p-1), p-1, p) != 1)
return false;
return true;
}
public static void main(String[]args) {
System.out.println( "enter a number to check if its prime or not");
if (isPrime(new Scanner(System.in).nextInt(), 100))
System.out.println("prime");
else
System.out.println("not a prime.");
}
}

[mosty friedman]

(0x01 & n) == 0

very interesting trick, thanks for the tip..but can you explain to me what does this part do???

[unutbu]

0x01 is hexadecimal notation for the number 1.
& is the bit-and operator.
n is an integer.

Think in binary. If n is even then its binary representation will end in a 0. 0x01 has a binary reprensentation that ends in a 1. If you bit-and 0 and 1, you get 0. So

(0x01 & n) == 0

is true if n is even. Similarly, the expression is false if n is odd. So it is a test if n is even or odd.

In the greater context of the previous post, the code is expressing the idea that numbers which are strictly less than 2 or even are not prime.

[mosty friedman]

0x01 is hexadecimal notation for the number 1.
& is the bit-and operator.
n is an integer.

Think in binary. If n is even then its binary representation will end in a 0. 0x01 has a binary reprensentation that ends in a 1. If you bit-and 0 and 1, you get 0. So

(0x01 & n) == 0

is true if n is even. Similarly, the expression is false if n is odd. So it is a test if n is even or odd.

In the greater context of the previous post, the code is expressing the idea that numbers which are strictly less than 2 or even are not prime.
to check if a number is even cant we just do this if( n%2 == 0 )...i;m sorry i'm not really familiar with the binary operators, can you please tell me in which situations they could become really helpful

[pp.]

to check if a number is even cant we just do this if( n%2 == 0 )...i;m sorry i'm not really familiar with the binary operators, can you please tell me in which situations they could become really helpful

A division operation takes more time (uses more CPU cycles) than a bitwise AND. At least, this used to be true for all processors of a few years ago.

[unutbu]

Sure, n%2 == 0 works too. I believe (0x01 & n)==0 may be faster however, since the bit-and operation is extremely easy for computers to do, while taking the modulus of a number is in general more complicated.


For information on what the bit-and operation does, perhaps see this page: http://en.wikipedia.org/wiki/Binary_and

The key idea is that 0 is associated with False, and 1 is associated with True. So 0 & 1 (sort-of) means False and True, which, according to the rules of logic, yields False (i.e. 0).

[pp.]

APL

(∼R∈R°.×R)/R←1↓ιR

No, I don't speak APL. It's from Wikipedia (http://en.wikipedia.org/wiki/APL_(programming_language)#APL_Glossary)

[tom66]

Efficient C version:



bool is_prime(int n)
{
int y = 2;
int m = (int)ceil(sqrt(n));

if(n == 0 || n == 1) return false;
if(n == 2) return true;

for(; y < m; y++)
{
if(y % n == 0)
return false;
}

return true;
}


Overly-complex and probably slower version:



bool is_prime(int n)
{
int y = 2;
int m = (int)ceil(sqrt(n));

if(n == 0 || n == 1) return false;
if(n == 2) return true;

for(; y < m; y++)
{
if((log(y) / log(2)) % 1 == 0)
((x & (y - 1)) == 1) ? (y + 0)
: return false;

if(y % n == 0)
return false;
}

return true;
}

[jimi_hendrix]

what does the semi-colen in the for loop do?

[Bichromat]

Efficient C version:



bool is_prime(int n)
{
int y = 2;
int m = (int)ceil(sqrt(n));

for(; y < m; y++)
{

if(y % n == 0)
return false;
}

return true;
}



This version is incorrect and quite inefficient : it gives wrong results for n<2, and it calculates y%n for n even, which is unnecessary.

[tom66]

Well, it worked for my Ulam spiral script which produced good results, identical to known good spirals. I did make a modification, I removed the second assignment in the loop. Square root is there because it's the HCF of that number, in any case.

I see what you mean for the dividing <2, I'll try to correct that.

[jimi_hendrix]

@ tom66

what does that ; in the for loop declaration do?

[snova]

@ tom66

what does that ; in the for loop declaration do?
Nothing. Ordinarily a for loop looks like:


for( INITIALIZATION ; CONDITION ; POST-BODY )

But there is no initialization code in this loop, so he leaves it out. But the semi-colon is still necessary.

[jimi_hendrix]

Nothing. Ordinarily a for loop looks like:


for( INITIALIZATION ; CONDITION ; POST-BODY )

But there is no initialization code in this loop, so he leaves it out. But the semi-colon is still necessary.

interesting...i thought it was one of those C triks that i never learned...

[Bichromat]

Well, it worked for my Ulam spiral script which produced good results, identical to known good spirals. I did make a modification, I removed the second assignment in the loop. Square root is there because it's the HCF of that number, in any case.

Oops, I meant it calculates n % y for every y (it's y % n in your code by the way, that's what confused me). When entering the loop, you should have established that n is not divisible by 2, so there's no use to test n % 4, n % 6 etc.
The loop should start with y = 3 and the increment should be 2, so as to test odd integers only (twice faster).

[efittery]

In J, the easiest to write test would be:

1 p: <some number>

which returns 1 if prime and 0 if not prime

1 p: 3
1

1 p: 5
1

1 p: 2147483658 which is ( 2^31)
1 p: 2147483647 which is ((2^31)-1)

now about bigger numbers, say like ((2^127-1) which is:
170141183460469231731687303715884105727

1 p: 170141183460469231731687303715884105727
1

slower

How about ((2^521) - 1) which is:

68647976601306097149819007990813932172694353001433 05
40939446345918554318339765605212255964066145455497 72
96311391480858037121987999716643812574028291115057 151

1 p: ((2x^521) - 1)
1

Really slow.

A better approach is needed to handle numbers like:

((2x^43112609) -1) which is a number that is 12978189 digits long.

Electronic Frontier Foundation is offering a $150,000 award to the first person or group to discover a 100 million digit prime number! See how GIMPS will distribute this award if we are lucky enough to find the winning 100 million digit prime.

Good luck

[samjh]

Ada

Naive algorithm.


with Ada.Text_IO, Ada.Integer_Text_IO, Ada.Command_Line;

use Ada.Text_IO, Ada.Integer_Text_IO, Ada.Command_Line;

procedure Prime is
Target : Integer;
Result : Boolean := True;
begin
Target := Integer'Value(Argument(1));

if Target > 1 then
for N in Integer range 2..(Target-1) loop
if Target mod N = 0 then
Result := False;
exit;
end if;
end loop;
else
Result := False;
end if;

if Result = True then
Put_Line("Prime");
else
Put_Line("Non-Prime");
end if;
end Prime;

To compile and run:
1. Install GNAT (sudo apt-get install gnat).
2. Save code into file: prime.adb
3. Compile using command: gnat make prime.adb
4. Usage: ./prime [integer]. Example: ./prime 10000

[ZuLuuuuuu]

Here is an algorithm in two languages, I wrote while doing Project Euler problems :)

Tcl:


proc is_prime {number} {
set j 2

while {$number % $j != 0} {
incr j
}

if {$j == $number} {
return 1
} else {
return 0
}
}

Smalltalk:


Integer extend [
isPrime [
| i |

i := 2.

[self \\ i = 0] whileFalse: [
i := i + 1.
].

(i = self) ifTrue: [
^true
] ifFalse: [
^false
].
]
]

[sujoy]

highly inefficient haskell code, but its uber simple :P



factors num = [x | x <- [1..num], num `mod` x == 0]
prime num = factors num == [1,num]

[Wybiral]

Python (a bit more pythonic)



from math import sqrt

def isprime(n):
highest = int(sqrt(n)) + 1
if n > 1 and all(n % x > 0 for x in range(2, highest)):
return True
else:
return False


This could easily be a one-liner, albeit less explicit and thus not Pythonic at all (true Python code should never look like this!) But just for kicks:


isprime = lambda n: n > 1 and all(n % x for x in range(2, int(n ** 0.5) + 1))

[Simian Man]

(* Ocaml *)

Printf.printf "Enter number: ";
let value = read_int () in
let is_prime x =
let bound = int_of_float (ceil (sqrt (float_of_int x))) in
let rec ip_aux x n =
if n > bound then true
else if (x mod n) == 0 then false
else (ip_aux x (n + 1))
in (ip_aux x 2)
in Printf.printf "%d is %s\n" value (if (is_prime value) then "prime" else "not prime")

[SirGe]

This thread is a bit stale, but I could not hold myself back...

A perl/regexp command line hack (with optimizations at that!):


$ perl -le 'print+((1x shift)=~/^1?$|^(11+?)\1+$/&&"not "),"prime"' <number>

Use it like so:


perl -le 'print+((1x shift)=~/^1?$|^(11+?)\1+$/&&"not "),"prime"' 315779

By the way, that's about the limit of how far it will work (unless you have extra patience and spare time :))

Enjoy figuring out how it works...

Dis Claimer: not my code, Abigail did it first, I think.

[roobie]

This is my contribution: (D v2)


#!/usr/bin/rdmd
import std.stdio;
import std.math;

bool isPrime(long n) {

int factors;

real cieling = sqrt(n);

if (n == 0) {
return false;
}

for (long i = 2; i <= cieling; ++i) {
if (factors != 0) {
return false;
}

if (n % i == 0) {
factors++;
while (n % i == 0) {
n /= i;
factors++;
}
}
}
return true;
}

void main() {
writeln(isPrime(0));
writeln(isPrime(1));
writeln(isPrime(2));
writeln(isPrime(3));
writeln(isPrime(1111111111111111111));
}

If you have the DMD d-compiler v2.x just run it as a script, i.e.

./<file name>.d

[Klaus Viuhka]

General, easy "sysadmin style" shell one-liner (gnu utils, not exactly programming language, but...)


seq 20 | factor | perl -ane 'printf "%s %sprime\n", $F[0], ($#F == 1) ? "" : "not "'

[KdotJ]

Just for the laughs... here it is in LOLcode:


HAI
CAN HAS STDIO?

GIMMEH VAR
I HAS A NUM
LOL NUM R 2

IM IN YR LOOP
UP NUM!!1
IZ NUM BIGGER THAN VAR? GTFO

I HAS A TEMP
LOL TEMP R VAR % NUM

IZ TEMP LIEK 0?
YARLY
VISIBLE Not Prime!
GTFO
KTHX
IM OUTTA YR LOOP

IS NUM LIEK VAR? VISIBLE Prime Number!
KTHXBYE



PS. It may be wrong lol, I haven't ever attempted to compile and run LOLcode.