CODEWITHSUNDEEP
python-3.x
sidchelseafan
sidchelseafan

Reputation: 49

printing prime numbers using only loops and if statements

What’s wrong with this code?

import math
y=1
z=y
while z>= 1 and z<1000 :
    z= 2*y + 1
    y=y+1
    for a in range (2,int(math.sqrt(z) + 1)):
        if z%a != 0:
            print(z)
        else:
            break

What’s wrong here? I keep getting composite numbers as well in my output.

Upvotes: 1

Views: 408

Answers (2)

Sohaib
Sohaib

Reputation: 4694

You are printing a number even if it is not divisible by one number but divisible by another number.

The print should be outside the loop.

 import math
 y=1
 z=y
 while z>= 1 and z<1000 :
      z= 2*y + 1
      y=y+1
      flag=0
      for a in range (2,int(math.sqrt(z) + 1)):
          if z%a == 0:
              flag=1
              break
      if flag==0:
          print z

Another way to improve your algorithm would be to move in multiples of six and check for numbers that are multipleofsix-1 and multiple of six+1 which would give you a much better efficiency. Except for 2 and 3 all other prime numbers could be found out in that range.

Further improvement would require you to maintain an array and store all previous primes and only divide by all primes below the square root of the number which you are checking.

There are still better improvisations like sieve of Eratosthenes and Atkins but these are the most basic that you can implement.

Upvotes: 1

wildwilhelm
wildwilhelm

Reputation: 5019

For z to be a prime number, it must be the case that there does not exist any number a such that 2 <= a <= sqrt(z) and a is a factor of z. I'd change your code to:

import math
y=1
z=y
while z>= 1 and z<1000 :
    z= 2*y + 1
    y=y+1
    if all(z%a != 0 for a in range (2,int(math.sqrt(z) + 1))):
        print(z)

Upvotes: 1

Related Questions