Find prime number to sortest loop condition

Question

I'm newbie in Python. When I study in loop condition, I got code for prime number given below

i = 13
j = 2
while(j <= (i/j)):
 if not(i%j): break
 j = j + 1
 if (j > i/j) : print i, " is prime"

Here I want logical to break while condition, if we want to find 13 is prime number or not we used loop range is 2 to 12. Here they used only 3 loop because of the loop condition while(j <= (i/j)). The loop structure is

 i  ==>  j  while(j <= (i/j))
 13      2  2<=6(13/2) true
 13      3  3<=4(13/3) true
 13      4  4<=3(13/4) false

My question is, how the condition 4<=3(13/4) to satisfy the loop to check prime number?

I want maths logical any one help me the clear explanation.

Answer 1

The important thing here is to note that if ij = n, then at least one of i, j is less than or equal to sqrt(n). Therefore, we only need to check factors up to and including sqrt(n). So to test whether 25 is prime, we need to test factors up to 5. To test 23, we would need to loop and test 2, 3, and 4, and then when we get to 5 we notice that we're > sqrt(23) and break. The test j > i/j is the same test, since j > i/j implies that j^2 > i.

Answer 2

I'm not sure what the issue is exactly, because the provided code should correctly return that 13 is a prime number. I also tested it with 97, and it worked just fine.

I think you will want to pay special attention to the modulus operator when trying to solve for primes. With the modulus operator, you will divide the left side of the modulus with the right side and will be returned the remainder. If the remainder is 0, then you know the number is not prime because it divides evenly with some number.

Example:

>>> 2 % 2
0
>>> 3 % 2
1

In the provided code:

i = 13
j = 2
while(j <= (i/j)):                      #1>>
    if not(i%j): break                  #2>>
    j = j + 1                           #3>>
    if (j > i/j) : print i, " is prime" #4>>

The while loop loops like the following (also note that without the decimal, the program will 'floor' the decimal to the lowest whole number):

Loop #1

1>> 2 is less than 6 (13/2), True so enter loop
2>> 13%2 = 1, no break
3>> j now equals 3
4>> 3 < 13/3, no print

Loop #2

1>> 3 is less than 4 (13/3), True so continue loop
2>> 13%3 = 1, no break
3>> j now equal 4
4>> 4 > 13/4, prints that the number is prime and proceeds to loop #3

Loop #3

1>> 4 is greater than 3 (13/4), so exit loop

To solve for a prime, you can follow these steps in their respective orders:

• If number is 2, the number is prime (#1)
• If number is divisible by two, number is not prime (#2)
• If number is divisible by 3, 5, 7, 9, etc (steps of 2), number is not prime (#3)

So you may get something like the following:

def get_prime(number):
    if number == 2:
        return True #Number is prime, exit method
    if number % 2 == 0:
        return False #Number is not prime, exit method
    for n in range(3, int(number), 2): #Start at 3, end at number, increment by 2
        if number % n == 0:
            return False #Number is not prime, exit method
    return True #Number passed all tests, is provably prime

The latter is preferred because we don't have to hold onto and increment 'throwaway variable' (j in this case). We increment the for loop by 2 for this, and also because it reduces the amount of time your computer needs to work to find the answer since any even number is divisible by 2 (referring back to step #2). For small numbers, however, (e.g. 13) you won't notice the difference.

∆