Print series of prime numbers in python

Question

I am trying to learn Python programming, and I'm pretty new at this.

I was having issues in printing a series of prime numbers from one to hundred. I can't figure our what's wrong with my code.

Here's what I wrote; it prints all the odd numbers instead of primes:

for num in range(1,101):
    for i in range(2,num):
        if (num%i==0):
            break
        else:
            print(num)
            break

Answer 1

First we find factor of that number

def fac(n):
  res = []
  for i in range(1,n+1):
    if n%i == 0:
res.append(i)

Script to check prime or not

def prime(n):
return(fac(n) == [1,n])

Script to print all prime number upto n

def prime_list(n):
  pri_list = []
  for i in range(1,n+1):
    if prime(i)
      pri_list.append(i)
return(pri_list)

Answer 2

The best way to solve the above problem would be to use the "Miller Rabin Primality Test" algorithm. It uses a probabilistic approach to find if a number is prime or not. And it is by-far the most efficient algorithm I've come across for the same.

The python implementation of the same is demonstrated below:

def miller_rabin(n, k):

    # Implementation uses the Miller-Rabin Primality Test
    # The optimal number of rounds for this test is 40
    # See http://stackoverflow.com/questions/6325576/how-many-iterations-of-rabin-miller-should-i-use-for-cryptographic-safe-primes
    # for justification

    # If number is even, it's a composite number

    if n == 2:
        return True

    if n % 2 == 0:
        return False

    r, s = 0, n - 1
    while s % 2 == 0:
        r += 1
        s //= 2
    for _ in xrange(k):
        a = random.randrange(2, n - 1)
        x = pow(a, s, n)
        if x == 1 or x == n - 1:
            continue
        for _ in xrange(r - 1):
            x = pow(x, 2, n)
            if x == n - 1:
                break
        else:
            return False
    return True

Answer 3

A Python Program function module that returns the 1'st N prime numbers:

def get_primes(count):
    """
        Return the 1st count prime integers.
    """
    result = []
    x=2
    while len(result) in range(count):
        i=2
        flag=0
        for i in range(2,x):
            if x%i == 0:
                flag+=1
                break
            i=i+1
        if flag == 0:
            result.append(x)
        x+=1
    pass
    return result

Answer 4

You need to check all numbers from 2 to n-1 (to sqrt(n) actually, but ok, let it be n). If n is divisible by any of the numbers, it is not prime. If a number is prime, print it.

for num in range(2,101):
    prime = True
    for i in range(2,num):
        if (num%i==0):
            prime = False
    if prime:
       print num

You can write the same much shorter and more pythonic:

for num in range(2,101):
    if all(num%i!=0 for i in range(2,num)):
       print num

As I've said already, it would be better to check divisors not from 2 to n-1, but from 2 to sqrt(n):

import math
for num in range(2,101):
    if all(num%i!=0 for i in range(2,int(math.sqrt(num))+1)):
       print num

For small numbers like 101 it doesn't matter, but for 10**8 the difference will be really big.

You can improve it a little more by incrementing the range you check by 2, and thereby only checking odd numbers. Like so:

import math
print 2
for num in range(3,101,2):
    if all(num%i!=0 for i in range(2,int(math.sqrt(num))+1)):
       print num

Edited:

As in the first loop odd numbers are selected, in the second loop no need to check with even numbers, so 'i' value can be start with 3 and skipped by 2.

import math
print 2
for num in range(3,101,2):
    if all(num%i!=0 for i in range(3,int(math.sqrt(num))+1, 2)):
        print num

Answer 5

Print n prime numbers using python:

num = input('get the value:')
for i in range(2,num+1):
    count = 0
    for j in range(2,i):
        if i%j != 0:
            count += 1
    if count == i-2:
        print i,

Answer 6

The fastest & best implementation of omitting primes:

def PrimeRanges2(a, b):
    arr = range(a, b+1)
    up = int(math.sqrt(b)) + 1
    for d in range(2, up):
        arr = omit_multi(arr, d)