Is Prime

iZuckonit posted @ 2012年3月23日 16:59 in C/C++ with tags c prime int , 1237 阅读

enter an int , judge whether it is Prime

#include <stdio.h>
#include "math.h"

int isPrime(int n)
{
	int i;
	if(n <= 1)
		return 0;
	else if (n == 3 || n == 2)
		return 1;
	else{
		for (i = 2; i <= sqrt(n); ++i){
			if(n % i == 0)
				return 0;
		}
	}

	/*
	same but simple
	@依云
	if(n < 2)
		return 0;
	for(i = 2;i <= sqrt(n); ++i){
		if(n % i == 0)
			return 0;
	}

	*/
	return 1;
}


int main(int argc, char const *argv[])
{
	
	int n;

	scanf("%d",&n);
	if (isPrime(n)){
		printf("%d is a prime\n", n);
	}
        else{
    	        printf("%d is not a prime\n", n);
        }

	return 0;
}

[回复]

依云说:
2012年3月23日 18:53

No positive even number except 2 is a prime and you should make use of this.

[回复]

依云说:
2012年3月23日 18:54

A neat Haskell solution:

import System.Environment (getArgs)

isPrime :: Integer -> Bool
isPrime 2 = True
isPrime x
| x <= 1 || even x = False
| otherwise = and [x `mod` i /= 0 | i <- [3, 5..truncate $ sqrt $ fromIntegral x]]

main = print . isPrime . read . head =<< getArgs

[回复]

依云说:
2012年3月23日 18:55

Another Haskell version, harder to understand but better in algrithm. Also note that the leading spaces have been striped by the commenting system.

import Control.Monad
import Control.Monad.Instances
isPrime = ap (all.((0 /=).).mod) $ flip takeWhile primes . (.join(*)) . flip (<=)
primes = 2 : filter isPrime [3,5..]

[回复]