Question #39903

An integer greater than 1 is said to be prime if it is divisible by only 1 and itself. For example,
2, 3, 5 and 7 are prime numbers, but 4, 6, 8 and 9 are not.
a) Write a function that determines whether a number is prime.
b) Use this function in a program that determines and prints all the prime numbers between
2 and 1,000.
c) Initially, you might think that n/2 is the upper limit for which you must test to see whether
a number is prime, but you need go only as high as the square root of n. Rewrite the program
and run it both ways to show that you get the same result.

Expert's answer

#python 2.7

def is_prime(n,root = True):

if root == True:

end = int(n**0.5+1)

else:

end = int(n/2+1)

for i in range(2,end):

if n%i == 0:

return False

return True

# determines and prints all the prime numbers between 2 and 1,000.

#the upper limit is sqrt(n)

for i in range(2,1000):

if(is_prime(i)):

print i

# determines and prints all the prime numbers between 2 and 1,000.

#the upper limit is n/2

for i in range(2,1000):

if(is_prime(i,False)):

print i

def is_prime(n,root = True):

if root == True:

end = int(n**0.5+1)

else:

end = int(n/2+1)

for i in range(2,end):

if n%i == 0:

return False

return True

# determines and prints all the prime numbers between 2 and 1,000.

#the upper limit is sqrt(n)

for i in range(2,1000):

if(is_prime(i)):

print i

# determines and prints all the prime numbers between 2 and 1,000.

#the upper limit is n/2

for i in range(2,1000):

if(is_prime(i,False)):

print i

## Comments

## Leave a comment