How do I write this program?

Question

Write a python program that finds all of the prime numbers between 1 and 100.

 

This is what I wrote:

print [n for n in xrange(1, 100) if n%n==0]

 

and it gave me a bunch of numbers from 1 to 100 but there are many numbers that aren't prime numbers. So how do I write this program? And please tell me the right answer. Thanks.

 

But do you have a shorter code than that? 

Answer 1

Use a helper function to see if a number is prime and first seed your prime list with [2, 3] :

 

primes = [2,3] ## seed the prime array

 

## create a helper function based on the prime array to see if the number is prime.

## if the number n passed to the function is mod 0 with any of the numbers in the 

##primes array, then return false.

## If the number n is not mod 0 with any of the numbers in the primes array then

## it is a new prime number

def isPrime(n):

   for num in primes:

      if n % num == 0:

         return False

   return True

 

## loop through the sequence 4..100 inclusive

## if isPrime() returns True then append the number to

## the primes array

def run():
   for n in range(4, 101):
      if isPrime(n):
         primes.append(n)
   print primes

if __name__ == "__main__":
   run()

Answer 2

Hi Sun,

 

The problem with your code is that "n%n" -- the modulus operator -- returns the remainder when "n" is divided by "n". Any number "n" is exactly divisible by itself, so the remainder is always 0. Therefore your code will print every number from 1 to 100.

 

I will propose an algorithm to solve the problem. I'll give it in pseudo-code, and leave it to you to Python it. I'm using "!" for a comment indicator.

 

loop for n = 1 to 100

  if n < 3 then            ! 1 & 2 are prime

    print n

  else

    is_prime = true            ! assume n is prime

    loop for i = 2 to n-1    ! a little more work than needed

      if n%i = 0 then            ! n is divisible by i

        is_prime = false        ! so n is not prime

        exit loop                  ! exit the inner loop on "i"

      endif

    next i

    if is_prime = true then

      print n

    endif

  endif

next n

 

Note the comment "a little more work that needed". We only need to go from i=2 to j, where j is the largest integer less than or equal to sqrt(n). But this is a small looping program and hardly worth the time to compute "j"; we can just use n-1.

 

Hope this helps.