6. Is Prime (Solution w/ visual indicator) - Edit: tweaked to handle large numbers


#1

Visualizing steps / debugging helps me understand what's going on.
Here's the code I used, that seems to work. My biggest concern about this code, is having to hard code in True / False values for <2 and == 2.

Update

The original code borks (my laptop eats itself) on really large numbers. I updated the code to use range up to int(square root of x). Assumption is that if a number has a clean square root, then the number is NOT prime anyways.

The updated code works with the included large number.

Here's the updated code:

from math import sqrt

def is_prime(x):
    print ("is %s a prime number?" % x)
    print ("We need to divide %s by every number up to %s \n" %(x, int(sqrt(x)) + 1))
    # x = abs(x)                  # As I understand it, the definition of primes was adjusted to exclude negative numbers

    if x < 2:                     # all numbers < 2 are not prime. 
        return False

    elif x == 2:                  # 2 is a prime number
        return True

    else:
        for n in range(2, int(sqrt(x)) + 2):            # sqrt halves the number of possibilities to iterate through. Adding 2, accomodates for any integer rounding issues.
            print ("%s / %s = " % (x, n) + str(x / n))  # print the number we're testing divided by the number in the for loop

            if (x % n) == 0:      # if the number we're testing / the current number in the loop equals 0,
                return False      # then this number is NOT prime. 
        return True               # If the previous IF condition never hits False, then the number IS prime.

print (is_prime(14712189313))

This results in the following:

is 14712189313 a prime number?
We need to divide 14712189313 by every number up to 121294 

14712189313 / 2 = 7356094656.5
14712189313 / 3 = 4904063104.333333
14712189313 / 4 = 3678047328.25
14712189313 / 5 = 2942437862.6
14712189313 / 6 = 2452031552.1666665
14712189313 / 7 = 2101741330.4285715
14712189313 / 8 = 1839023664.125
14712189313 / 9 = 1634687701.4444444
14712189313 / 10 = 1471218931.3
14712189313 / 11 = 1337471755.7272727
14712189313 / 12 = 1226015776.0833333
14712189313 / 13 = 1131706870.2307692
14712189313 / 14 = 1050870665.2142857
14712189313 / 15 = 980812620.8666667
14712189313 / 16 = 919511832.0625
14712189313 / 17 = 865422900.7647059
14712189313 / 18 = 817343850.7222222
14712189313 / 19 = 774325753.3157895
14712189313 / 20 = 735609465.65
14712189313 / 21 = 700580443.4761904
14712189313 / 22 = 668735877.8636364
14712189313 / 23 = 639660404.9130435
14712189313 / 24 = 613007888.0416666
14712189313 / 25 = 588487572.52
14712189313 / 26 = 565853435.1153846
14712189313 / 27 = 544895900.4814814
14712189313 / 28 = 525435332.60714287
14712189313 / 29 = 507316872.86206895
14712189313 / 30 = 490406310.43333334
14712189313 / 31 = 474586752.0322581
.......
14712189313 / 121288 = 121299.62826495613
14712189313 / 121289 = 121298.62817732853
14712189313 / 121290 = 121297.62810619177
14712189313 / 121291 = 121296.62805154546
14712189313 / 121292 = 121295.62801338917
14712189313 / 121293 = 121294.62799172252
14712189313 / 121294 = 121293.62798654509
True
[Finished in 0.7s]

Here's original code:

def is_prime(x):
    print ("is %s a prime number?\n" % x)
    # x = abs(x)                  # As I understand it, the definition of primes was adjusted to exclude negative numbers

    if x < 2:                     # all numbers < 2 are not prime. 
        return False

    elif x == 2:                  # 2 is a prime number
        return True

    else:
        for n in range(2, x):                           # for each numer from 2, (because we already tested it), up to x
            print ("%s / %s = " % (x, n) + str(x / n))  # print the number we're testing divided by the number in the for loop

            if (x % n) == 0:      # if the number we're testing / the current number in the loop equals 0,
                return False      # then this number is NOT prime. 
        else:
            return True     # else applies to the for loop, so we can continue iterating until we hit a true value. If the previous IF condition never hits False, then the number IS prime.

print (is_prime(47))

This results in the following:

is 47 a prime number?

47 / 2 = 23.5
47 / 3 = 15.666666666666666
47 / 4 = 11.75
47 / 5 = 9.4
47 / 6 = 7.833333333333333
47 / 7 = 6.714285714285714
47 / 8 = 5.875
47 / 9 = 5.222222222222222
47 / 10 = 4.7
47 / 11 = 4.2727272727272725
47 / 12 = 3.9166666666666665
47 / 13 = 3.6153846153846154
47 / 14 = 3.357142857142857
47 / 15 = 3.1333333333333333
47 / 16 = 2.9375
47 / 17 = 2.764705882352941
47 / 18 = 2.611111111111111
47 / 19 = 2.473684210526316
47 / 20 = 2.35
47 / 21 = 2.238095238095238
47 / 22 = 2.1363636363636362
47 / 23 = 2.0434782608695654
47 / 24 = 1.9583333333333333
47 / 25 = 1.88
47 / 26 = 1.8076923076923077
47 / 27 = 1.7407407407407407
47 / 28 = 1.6785714285714286
47 / 29 = 1.6206896551724137
47 / 30 = 1.5666666666666667
47 / 31 = 1.5161290322580645
47 / 32 = 1.46875
47 / 33 = 1.4242424242424243
47 / 34 = 1.3823529411764706
47 / 35 = 1.3428571428571427
47 / 36 = 1.3055555555555556
47 / 37 = 1.2702702702702702
47 / 38 = 1.236842105263158
47 / 39 = 1.205128205128205
47 / 40 = 1.175
47 / 41 = 1.146341463414634
47 / 42 = 1.119047619047619
47 / 43 = 1.0930232558139534
47 / 44 = 1.0681818181818181
47 / 45 = 1.0444444444444445
47 / 46 = 1.0217391304347827
True
[Finished in 0.0s]

#2

If you are concerned with elegance then use Fermat's little thereom. It's a shorter solution.


#3

This topic was automatically closed 7 days after the last reply. New replies are no longer allowed.