How could I check if a number is a prime number? [duplicate]

This question already has answers here: Closed 11 years ago.

Possible Duplicate:

Simple Prime Generator in Python

First I will prompt user to input any number. Then my code will check whether does the number input by the user is a Prime number not.

Here is my codes:

num = int(raw_input("Input any of the number you like:"))
for x in range(2, int(num**0.5)+1):
    if num % x == 0:
        print "It is not a prime number"
    else:
        print "It is a prime number"

But question is I cant seem to get the output for 2 and 3. And when I randomly input any numbers like 134245, the system will output alot o开发者_StackOverflowf sentences. And I do not know why?

Appreciate any kind souls to help me up :)

---

import urllib
tmpl = 'http://www.wolframalpha.com/input/?i=is+%d+a+prime+number'
def is_prime(n):
    return ('is a prime number' in urllib.urlopen(tmpl % (n,)).read())

---

you should stop once num % x == 0 is true (no need for further testing) and print 'it is a prime number' only if the loop completed without anything printed before.

---

A number is prime if it only divides by 1 and itself. A pseudocode follows:

boolean prime = true;
for (int i = 2; i * i <= num; i++)
   if (num % i == 0) {
      prime = false;
      break;
   }

if (prime)
  println("It is prime!");
else 
  println("It is not prime!");

---

Look at your code like this:

num = ...
for x in range(2, int(num**0.5)+1):
    print something

The body of the loop is executed at every iteration. That means you're printing something at every iteration, i.e. for each x that you check to see if it's a factor of num, you print. That's not what you should be doing; in order to determine whether a number is prime, you check all possible factors first, then print your result. So you shouldn't be printing anything until after the loop.

---

But question is I cant seem to get the output for 2 and 3.

You're looping from 2 to ceil(sqrt(n)). For 2 and 3, this is an empty range, hence no iteration happens. Either special-case it or rewrite the code such that it assumes that n is prime and tries to disprove it in the loop.

the system will output alot of sentences.

You're printing on every iteration. Instead, use a boolean flag (or a premature return, if you factor it out into a function) to determine prime-ness and print once, after the loop, based on that prime.

---

Your code is not structured well-- the algorithm continues to loop all the way up to the top of your range, even if you already know that the number is composite, and it also prints some result on each iteration when it should not.

You could put the logic into a function and return True or False for prime-ness. Then you could just check the result of the function in your if statement.

def is_prime(num):
    for x in range(2, int(num**0.5)+1):
        if num % x == 0:
            return False
    return True

num = int(raw_input("Input any of the number you like:"))
if not is_prime(num):
    print "It is not a prime number"
else:
    print "It is a prime number"

---

Here are two Python routines for calculating primes. (Hint: Google for Sieve of Eratosthenese):

def pythonicSieve(maxValue):
    """
    A Pythonic Sieve of Eratosthenes - this one seems to run slower than the other.
    see http://love-python.blogspot.com/2008/02/find-prime-number-upto-100-nums-range2.html
    """
    return [x for x in range(2,maxValue) if not [t for t in range(2,x) if not x%t]]

def sieveOfEratosthenes(maxValue):
    """
    see http://hobershort.wordpress.com/2008/04/15/sieve-of-eratosthenes-in-python/
    """
    primes = range(2, maxValue+1)
    for n in primes:
        p = 2
        while n*p <= primes[-1]:
            if n*p in primes:
                primes.remove(n*p)
            p += 1
    return primes