How could I check if a number is a prime number?

Question

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 of sentences. And I do not know why?

Appreciate any kind souls to help me up :)

There are many python-prime questions here. It rather sounds like you need to do some more experimenting with python itself before you're ready to have a go at this particular problem. :) — bzlm, Sep 17 '11 at 17:25
note that `range(2, x)` only loops to x-1 (see `help(range)`) and `range(2,2)` evaluates to an empty list thus your loop body is never executed for `num` equal to 2 or 3. — Andre Holzner, Sep 17 '11 at 19:17

score 5 · Answer 1 · answered Sep 17 '11 at 17:38

5

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

answered Sep 17 '11 at 17:38

habnabit

9,906
3
32
26

Note that you can optimize this code by rewriting it `import urllib` `def is_prime(n, _urlopen=urllib.urlopen):` `return ('is a prime number' in _urlopen('http://www.wolframalpha.com/input/?i=is+%d+a+prime+number' % (n,)).read())`. Good job overall, though. – Mike Graham Sep 17 '11 at 18:23

score 1 · Answer 2 · answered Sep 17 '11 at 17:24

1

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.

answered Sep 17 '11 at 17:24

Andre Holzner

18,333
6
54
63

Sorry! How to I do that? Cause I tried alot of way like break? But couldnt stop. – user950472 Sep 17 '11 at 17:34
@user950472: Break should have worked. Perhaps you used it in the wrong place? Maybe you should post that version of your code so we can tell you if you went wrong somewhere. – Platinum Azure Sep 17 '11 at 17:34
Here is my code: (I realize I can Stop it! Thanks!) 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" break But now another problem is why cant I compute 1, 2 and 3? Sorry! I just dont understand! – user950472 Sep 17 '11 at 17:42
You can/should immediately return once you found a divisor. If you reach the code after the loop this means you have not found a divisor, hence the number is prime. Platinum Azure's answer gives a concrete code example. If you don't return, you should at least break AND set a flag that you have found a divisor in order NOT to print that this is a prime after reaching the code after the loop. – Andre Holzner Sep 17 '11 at 19:13

score 0 · Answer 3 · answered Sep 17 '11 at 17:23

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!");

Platinum Azure · Answer 4 · 2011-09-17T17:33:59.110

0

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"

edited Sep 17 '11 at 17:33

answered Sep 17 '11 at 17:25

Platinum Azure

45,269
12
110
134

Not wrong, just a bit inefficient (but so is the method you propose, compared with sieves). – Sep 17 '11 at 17:27
It's wrong if it prints out "It is a prime number" or "It is not a prime number" for each number from 2 to the square root rounded up... :-) – Platinum Azure Sep 17 '11 at 17:31
Yes, that part is wrong (or simply too eager to share it's progress ^^). The part about looping over the whole range isn't wrong though. – Sep 17 '11 at 17:33
I'll clarify my answer to use a word different from "algorithm", since my issue is not with the calculations but with the way his code is laid out. – Platinum Azure Sep 17 '11 at 17:33
Icic.But I was told to print out the as "It is not a prime number" or "It is a prime number", thus I couldnt use T or F. – user950472 Sep 17 '11 at 17:36
@user950472: I'm not PRINTING the `True` or `False` result. I'm still printing the required output. How you get there doesn't matter[1] as long as you get the right answer. [1] Except eventually you'll start to care about efficiency, and then the game changes a bit. – Platinum Azure Sep 17 '11 at 17:38
Also, my code is wrong for the case of `1`, which is considered not prime. You'll need to add a special case for that. – Platinum Azure Sep 17 '11 at 17:38

score 0 · Answer 5 · answered Sep 17 '11 at 17:25

0

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.

answered Sep 17 '11 at 17:25

David Z

128,184
27
255
279

That Means must I write If-Else statements below the For loop or above it? – user950472 Sep 17 '11 at 17:36
Remember that code is executed from top to bottom ;-) – David Z Sep 17 '11 at 17:38
Erm.. It the code something like this? if num == 2 or 3: print "It is a prime number" elif num == 1: print "It is not a prime number" else: none – user950472 Sep 17 '11 at 17:53

score 0 · Answer 6 · answered Sep 17 '11 at 17:26

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.

score 0 · Answer 7 · answered Sep 17 '11 at 17:35

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

Oh! Thanks:) But is there any way I can dont use def? – user950472 Sep 17 '11 at 17:38 — user950472, Sep 17 '11 at 17:38

How could I check if a number is a prime number?

7 Answers7