9 Replies - 516 Views - Last Post: 04 November 2012 - 11:49 PM Rate Topic: -----

#1 cb1992  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 13
  • Joined: 01-November 12

Checking for prime with given method!

Posted 01 November 2012 - 02:21 PM

Im having some trouble with my code which has to take an integer from user input, and then check whether it is prime or not. I have been instructed to use the following method:

'This should be done by checking the remainder obtained when dividing the number n by 2 and then by all odd numbers between 3 and n/2; the number will be prime if and only if all of the remainders are non-zero.'

My problems are that, the code seems to work partially, I test with numbers 13, 131, 20, 21, which are all returned correctly, however if I enter 35 (which isnt prime) the code returns as not prime.

I also get this error if I enter the value 3 (although I believe this is because of the method we have been told to use the number is too small).

Here is my code:
num = int(input("Enter number: "))

if num%2 != 0 :
    for i in range(3, num/2, 2) :
        if num%i != 0 :
            prime = True
            break
        else :
            prime = False
            break
else :
    prime = False

if prime :
    print('Prime')
else :
    print('Not Prime')



Any help would be much appreciated!

Made a typo, 35 is returned as prime, my mistake.

Is This A Good Question/Topic? 0
  • +

Replies To: Checking for prime with given method!

#2 sepp2k  Icon User is offline

  • D.I.C Lover
  • member icon

Reputation: 2149
  • View blog
  • Posts: 3,304
  • Joined: 21-June 11

Re: Checking for prime with given method!

Posted 01 November 2012 - 04:15 PM

After the user enters a number the following steps will happen:

If the number is divisible by 2, you say it's not a prime number (note that this is not quite correct because 2 itself is both divisible by 2 and a prime number). Otherwise you check whether it's divisible by 3. If it is, you say it's not prime. If it isn't, you say it is prime. Either way you never check any number above 3 because you break out of the loop in both cases.
Was This Post Helpful? 0
  • +
  • -

#3 cb1992  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 13
  • Joined: 01-November 12

Re: Checking for prime with given method!

Posted 02 November 2012 - 10:38 AM

View Postsepp2k, on 01 November 2012 - 04:15 PM, said:

After the user enters a number the following steps will happen:

If the number is divisible by 2, you say it's not a prime number (note that this is not quite correct because 2 itself is both divisible by 2 and a prime number). Otherwise you check whether it's divisible by 3. If it is, you say it's not prime. If it isn't, you say it is prime. Either way you never check any number above 3 because you break out of the loop in both cases.


Thanks for your input mate, any ideas how I can correct this code? I dont know how to go about checking all the odd numbers, maybe create a function with it and call it in with the argument num?
Was This Post Helpful? 0
  • +
  • -

#4 Tayacan  Icon User is offline

  • D.I.C Regular
  • member icon

Reputation: 145
  • View blog
  • Posts: 275
  • Joined: 18-January 11

Re: Checking for prime with given method!

Posted 02 November 2012 - 10:59 AM

Mhmm, there are a few things to fix here. You can look at it this way:

Assume that the number is prime. Then try to disprove that.
num = int(input("Enter number: "))
prime = True

if num % 2 == 0 and num != 2: # Remember, 2 is a prime too.
    prime = False # It's even, so not prime
    
for i in range(3, num/2, 2):
    if num % i == 0:
        prime = False # We succesfully divided the number by something, so it's not a prime
        break

if prime :
    print('Prime')
else :
    print('Not Prime')


Was This Post Helpful? 0
  • +
  • -

#5 cb1992  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 13
  • Joined: 01-November 12

Re: Checking for prime with given method!

Posted 03 November 2012 - 11:21 AM

Thanks for the reply pal! However I just ran the revised code that you posted, and it still returns 35 as a prime number, is it perhaps the method that I am having to use that is flawed as I have tried a few different methods now (loop wise etc) so I am beginning to think that the method of:

'This should be done by checking the remainder obtained when dividing the number n by 2 and then by all odd numbers between 3 and n/2; the number will be prime if and only if all of the remainders are non-zero.'

I have to specifically use this method and want to understand why the code isnt working so I can progress in learning python.

Once again big thanks for any help, very much appreciated.
Was This Post Helpful? 0
  • +
  • -

#6 sepp2k  Icon User is offline

  • D.I.C Lover
  • member icon

Reputation: 2149
  • View blog
  • Posts: 3,304
  • Joined: 21-June 11

Re: Checking for prime with given method!

Posted 03 November 2012 - 12:10 PM

View Postcb1992, on 03 November 2012 - 07:21 PM, said:

Thanks for the reply pal! However I just ran the revised code that you posted, and it still returns 35 as a prime number


Are you sure? When I run the code that Tayacan posted and enter 35, I get back "Not Prime".
Was This Post Helpful? 0
  • +
  • -

#7 cb1992  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 13
  • Joined: 01-November 12

Re: Checking for prime with given method!

Posted 04 November 2012 - 01:31 PM

View Postsepp2k, on 03 November 2012 - 12:10 PM, said:

View Postcb1992, on 03 November 2012 - 07:21 PM, said:

Thanks for the reply pal! However I just ran the revised code that you posted, and it still returns 35 as a prime number


Are you sure? When I run the code that Tayacan posted and enter 35, I get back "Not Prime".


Yep, here is a link to a screenshot I just took, with the code and a few example runs, any ideas? Unless im being an absolute idiot and made an error when copying and pasting the code, but I cant see any difference?

Thanks for any help as always!

Posted Image
Was This Post Helpful? 0
  • +
  • -

#8 sepp2k  Icon User is offline

  • D.I.C Lover
  • member icon

Reputation: 2149
  • View blog
  • Posts: 3,304
  • Joined: 21-June 11

Re: Checking for prime with given method!

Posted 04 November 2012 - 01:54 PM

Compare the indentation of Tayacan's code with that of yours. You did make a copy and paste error: The for loop is not supposed to be inside the if statement.

This post has been edited by sepp2k: 04 November 2012 - 01:55 PM

Was This Post Helpful? 0
  • +
  • -

#9 cb1992  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 13
  • Joined: 01-November 12

Re: Checking for prime with given method!

Posted 04 November 2012 - 02:23 PM

View Postsepp2k, on 04 November 2012 - 01:54 PM, said:

Compare the indentation of Tayacan's code with that of yours. You did make a copy and paste error: The for loop is not supposed to be inside the if statement.


My mistake! Thanks very much everyone for your help I have learnt from this!

Much appreciated!
Was This Post Helpful? 0
  • +
  • -

#10 Tayacan  Icon User is offline

  • D.I.C Regular
  • member icon

Reputation: 145
  • View blog
  • Posts: 275
  • Joined: 18-January 11

Re: Checking for prime with given method!

Posted 04 November 2012 - 11:49 PM

It makes sense if you consider the method I described as well. The if statement tests if its not a prime. Then, the for loop tests some other things that would make it not prime.

A way to make this more efficient would be to put the code inside a function, and then instead of setting the prime variable to false, you can just return false.
Was This Post Helpful? 0
  • +
  • -

Page 1 of 1