CODEWITHSUNDEEP
pythonmath
miloLovesCamelCase
miloLovesCamelCase

Reputation: 13

efficiently finding prime numbers in python

here is my code:

def findPrimes():
   prime=True
   c=0
   n=1
   while n<14:
        n=n+1
        for i in range(1,n):
            if n%i==0:
                prime=False
        if prime==True:
            print(n)
   while c==0:
        n=n+1
        if (n%2==0) or (n%3==0) or (n%5==0)or (n%7==0)or (n%11==0)or (n%13==0):
            c=0#this does nothing
        else:
            for i in range(5,int(n**0.5),2):
                if n%i==0:
                    break
            print(n)
findPrimes()

it should output: 2 3 5 7 11 13 17 ... Instead, I get: 17 19 23 29 31 37 41 43 47 ... or(with break in a different indent): 2 3 4 5 6 7 8 9 10 11 12 13 17 19 ... why is this?

Upvotes: 1

Views: 11082

Answers (9)

CODE WRITER
CODE WRITER

Reputation: 1

Many solutions are pointing you to the sieve algorihim.

However, if you're needing a simple brute-force implementation you can write your code much more cleanly which will make finding errors and mistakes much easier.

Here's a cleaner brute-force implmentation:

num = 11
  
# If given number is greater than 1
if num > 1:
  
    # Iterate from 2 to n / 2
    for i in range(2, int(num/2)+1):
  
        # If num is divisible by any number between
        # 2 and n / 2, it is not prime
        if (num % i) == 0:
            print(num, "is not a prime number")
            break
    else:
        print(num, "is a prime number")
  
else:
    print(num, "is not a prime number")

Upvotes: 0

Farhan Khursheed
Farhan Khursheed

Reputation: 11

The most efficient way to find prime numbers is this:

def prime(nums,no_of_recursion):
  if(nums):
    print(min(nums),end=", ")
    nums-=set(range(min(nums), max(nums)+1, min(nums)))
    no_of_recursion=no_of_recursion+1
    prime(nums,no_of_recursion)
  else:
    print('\nTotal recursions: '+str(no_of_recursion))


limit=101
no_of_recursion=0
nums=set(range(2,limit+1))
prime(nums,no_of_recursion)

Output:

2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 
Total recursions: 26

Upvotes: 1

Abhijit
Abhijit

Reputation: 1

nums = int(input("enter the number "))
for i in range(2,nums):
    if nums % i  == 0:
        print("Its not a prime no ")
        break
else:
    print("prime no ")

Upvotes: -1

Avi
Avi

Reputation: 1

#Efficient way of Prime number -------->>>>>
try:
    num = int(input('Enter number : '))
    if(num>1):
        for i in range(2,num):
            if (num%i==0):
                print(f'{num} is not a Prime Number...!')
                break
        else:
            print(f'{num} is a Prime Number...!')
    elif num==0:
        print(f'{num} is conpositive number')
    elif num == 1:
        print(f"{num} is not considered as prime or composite")
    else:
        print('Invalid input')
except:
    print('Invalid input')

Upvotes: 0

Anubhav
Anubhav

Reputation: 1

If you want to check a number is prime or not , let's check the number 13.

a = 13
for b in range(2,a) :
    if a % b == 0 :
        print("not prime")
        break
    else :
        print("prime")

Upvotes: -2

Indrajith Sundaram
Indrajith Sundaram

Reputation: 31

The best efficient way to find the Prime numbers is to use the Sieve of Eratosthenes algorithm.

Here is the code:

n = int(input("enter the number upto which to find: "))
sieve = set(range(2, n+1))
while sieve:
    prime = min(sieve)
    print(prime, end="\t")
    sieve -= set(range(prime, n+1, prime))
print()

Explanation:

  • First, get the upper limit of the range

  • A variable of set type is assigned to eliminate the duplicates

  • As we know 0,1 are not prime numbers, so we don't count them i.e (2,n+1)

  • We take minimum element as prime and print it

  • Now, if 2 is prime, all of the multiples of 2 cannot be prime. So we neglect the multiples of 2. Same as the following 3,5,7 etc...

  • So, all the remaining numbers are added to sieve i.e the remaining numbers are prime numbers.

Upvotes: 3

cwalsh003
cwalsh003

Reputation: 79

Using the Sieve of Eratosthenes an efficient way to find all primes. It is proven that you only have to check up to sqrt(n) items. 

def primes_sieve2(limit):
a = [True] * limit                   # Initialize the primalitylist
a[0] = a[1] = False

for (i, isprime) in enumerate(a):
    if isprime:
        yield i
        for n in xrange(i*i, limit, i):     # Mark factors non-prime
            a[n] = False

Upvotes: 1

user2782067
user2782067

Reputation: 422

this is all you need.

def primes(n):
        primeslist = [2]
        for i in range (2,n):
            p = 1
            for j in primeslist:

                if (i%j) == 0:
                    p = 0
                    break
            if p == 1:
                primeslist.append(i)
        return primeslist

    primeslist = primes(66)
    print(primeslist)

NOTES:

  • you only need to check division by all previous primes in the list to find whether a number is prime.
  • is prime flag should be set before second loop.
  • n is the number that you want to stop checking for primes at. otherwise your program will go on forever.
  • computing primes can only be so efficient. I found primes (99999) in about 7 seconds on my setup.
  • You can further limit the algorithm to checking only 1 to sqrt(n) for divisibility. 
primeslist = primes(66)
print(primeslist)

[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61]

Upvotes: 0

Xero Smith
Xero Smith

Reputation: 2076

Consider this block of code:

while n<14:
        n=n+1
        for i in range(1,n):
            if n%i==0:
                prime=False

prime will be equal to false for every iteration there because

x % 1 == 0 for all x

Upvotes: 0

Related Questions