Python: To check if a particular number is a prime number

Question

I'm fairly a beginner in Python. Please help in getting the right and accurate code; I am trying to directly translate directly into Python terms the following mathematical statement:

let Q = [2,...,n-1] if there exist p,q ∈ Q | pq = n, then n is not a prime number

where n is any integer I want to check if it's prime or not

Here's my python code, please i tried using random.randint() to go through the list, i am getting wrong results (it checks a number but returns all positive integers as prime numbers)

import random

def primechecker(anumber):
    
    if anumber <= 1:
        print('1 is not a prime number, \n*2Input a positive integer greater than 1')
    
    p = random.randint(2,anumber)
    q = random.randint(2,anumber)
    if p*q==anumber:
        print('%d is not a prime number'%anumber)
    
    else:
        print('%d is a prime number ! :-)'%anumber)
        
primechecker(12)

@timgeb, its not a homework. im a math student just learning python... i just need help that's all — native_Dave, Jul 22 '20 at 16:00
Please see: https://stackoverflow.com/questions/1801391/how-to-create-the-most-compact-mapping-n-%e2%86%92-isprimen-up-to-a-limit-n — Raiyan Chowdhury, Jul 22 '20 at 16:08
If you're a math student, you should know that this is not a proper way to check if a number is prime. — Barmar, Jul 22 '20 at 16:12
[Sieve of Eratosthenes](https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes) — Barmar, Jul 22 '20 at 16:13

Luke Storry · Answer 1 · 2020-07-22T19:53:33.767

Your issue is that you are only checking one single set of p and q, so you only get the "not a prime number" output if you are very lucky and p*q happens to equal anumber on that first go.

The way that most very-simple prime-checkers works is to go sequentially between 0 and the square root of the test number, for both p and q, and rule out all possible factors. There are loads of other ways of checking for primarity though.

However, because computers are fast, you can keep the random choices, and just try a few thousand times, for small numbers the chances are you will probably be correct! Going through properly is still the best way.

(Disclaimer - this is not a real solution, just an example of using random in a more-correct way)

I've added a for loop to your code, which if it finds a match, will print and then do an early return from the function, or if it still hasn't found a hit after 10000 random tries, says that is is maybe prime.

import random

def primechecker(anumber):
    
    if anumber <= 1:
        print('1 is not a prime number, \n*2Input a positive integer greater than 1')
    
    for _ in range(10000):
      p = random.randint(2,anumber)
      q = random.randint(2,anumber)
      if p*q==anumber:
          print('%d is not a prime number'%anumber)
          return

    print('%d is maybe a prime number ! :-)'%anumber)
        
        
        
primechecker(70)import random

def primechecker(anumber):
    
    if anumber <= 1:
        print('1 is not a prime number, \n*2Input a positive integer greater than 1')
    
    for _ in range(10000):
      p = random.randint(2,anumber)
      q = random.randint(2,anumber)
      if p*q==anumber:
          print('%d is not a prime number'%anumber)
          return

    print('%d is probably a prime number ! :-)'%anumber)
        
        
        
primechecker(70)
          

import random

def primechecker(anumber):
    
    if anumber <= 1:
        print('1 is not a prime number, \n*2Input a positive integer greater than 1')
    
    for _ in range(10000):
      p = random.randint(2,anumber)
      q = random.randint(2,anumber)
      if p*q==anumber:
          print('%d is not a prime number'%anumber)
          return

    print('%d is probably a prime number ! :-)'%anumber)
        
        
        
primechecker(7)        
primechecker(99)        
primechecker(90)

Give it a try here -> https://repl.it/@LukeStorry/63038315

As you can see, it isn't very accurate for larger numbers, the way to go would be to not use random, but go sequentially, but this is a nice thing to try if you're learning python.

The chance of finding two factors that multiply to the number is really low. It would be better to test a single random number and use modulus. — Barmar, Jul 22 '20 at 16:15
I know. The point here isn't to write the best prime-checker, @Barmar is just learning python, and is using this maths as a way of doing that. The question was asking why their attempt wasn't working, so I answered the code problem (only checking once), before adding a fun extension (checking many times). I even say in my answer that it's not the best solution, multiple times, but is still a fun little script, with learning potential. — Luke Storry, Jul 22 '20 at 16:19
Instead of the link to repl.it, could you make your code executable here with Stack Snippet? — Barmar, Jul 22 '20 at 16:22
As I said, all you're doing is randomly shooting in the dark, and if nothing hits, it says nothing is there. You're never going to be entirely sure when using random, unless you go methodically through every option. — Luke Storry, Jul 22 '20 at 19:12
My point is that unless the numbers are small the chance you'll pick the right pair of factors is infinitessimal. For my example, you'd have to do more than 200,000 iterations to have a 50% chance of detecting that 23x29 is composite. — Barmar, Jul 22 '20 at 19:36
Yeah! Correct! So a solution using `random` is unfeasible, you need to iterate one-by-one. — Luke Storry, Jul 22 '20 at 19:50
Thank you so much @LukeStorry, really helpful!! you really helped in refining my line of thinking — native_Dave, Jul 22 '20 at 20:16

Sayandip Dutta · Accepted Answer · 2020-07-22T16:21:07.097

I hope you know how it is generally done, i.e. iterating through 2 to n-1 and checking if the number is divisible by any of the ones in range.

Now, in order to actualize the statement of primes, random is not really a solution, you may have to wait extremely long amount of time before you get a match if at all, and when there isn't a match, there's almost no way to tell except for storing all the previous guesses somewhere.

So you could do, one thing, try getting all combinations of p and q in the range, using itertools.combinations:

from itertools import combinations

def primechecker(number):
    if number <= 1: return "Please enter number > 1"

    for p, q in combinations(iterable=range(2,number), r=2):
        if p*q == number:
            return f"Not prime. {p} * {q} = {number}"

    else:
        return "Prime"

Now check:

>>> primechecker(1)
'Please enter number > 1'

>>> primechecker(15)
'Not prime. 3 * 5 = 15'

>>> primechecker(17)
'Prime'

Thank you so much @Sayandip Dutta ...this was particularly helpful...it is evident now that the precise tool that i needed was the [The Itertools.Combinations] (https://docs.python.org/3/library/itertools.html#itertools.combinations). Thanks for the help! — native_Dave, Jul 22 '20 at 20:14
the `primechecker` didnt work for 4, it returned it has a prime, but then i tried the `combinations with replacement` ...it now works. thanks again — native_Dave, Jul 22 '20 at 21:28

Python: To check if a particular number is a prime number

2 Answers2