1

My code will spit out clearly non prime numbers and im trying to figure out why

when I run the code, it outputs the prime numbers, but also occasionally output non primes too

x = 1
a = 4
b=2
#prints 2
print(2)
#prints 3
print(3)
#whilst x is under 1000, the next section of code will run
while x < 100:
    #sets b to 2
    b = 2
    #will repeat aslong as b is less than a
    while b < a:
       #if a can be divided by b with no remainder
        if a % b == 0:
            #adds 1 to a
            a = a+1
            #if not will add one to b
        else:
            b = b+1
    print(a)
    a = a+1
    x = x+1
nassim
  • 1,547
  • 1
  • 14
  • 26
John Beem
  • 29
  • 2
  • 1
    Possible duplicate of [Print series of prime numbers in python](https://stackoverflow.com/questions/11619942/print-series-of-prime-numbers-in-python) – Woodrow May 10 '19 at 19:44
  • Compare your code to the [example code for Trial Division](https://en.wikipedia.org/wiki/Trial_division#Method). – Fred Larson May 10 '19 at 19:44
  • To go off of @FredLarson's comment: I'd expect something like Trial Division or [Euler's Totient function](https://rosettacode.org/wiki/Totient_function#Python) - your code as it currently stands looks to have a few gaps in establishing primality. You may also find the [Pseudocode for Wikipedia's Primality test article](https://en.wikipedia.org/wiki/Primality_test#Pseudocode) helpful. – esqew May 10 '19 at 19:46
  • 4
    the logical problem with your code is that you're not trying all possible divisors, because you're failing to reset the divisor `b` to `2` after finding a divisor and moving on to the next `a` to try. – Robin Zigmond May 10 '19 at 19:47
  • If the 2 numbers are in base 8, then you're fine :p. – CristiFati May 10 '19 at 20:00

1 Answers1

1

Take a look:

x = 1
a = 4
#prints 2
print(2)
#prints 3
print(3)
#whilst x is under 1000, the next section of code will run
while x < 100:
    #sets b to 2
    b = 2
    #will repeat aslong as b is less than a
    while b < a:
       #if a can be divided by b with no remainder
        if a % b == 0:
            #adds 1 to a
            a = a+1

            b = 2  # <-- Point is here!
            # When a and b are not coprimes, we have to go back
            # and look for all possible values for b again for this new value of a.

            #if not will add one to b
        else:
            b = b+1
    print(a)
    a = a+1
    x = x+1
Ali Tou
  • 2,009
  • 2
  • 18
  • 33