find prime numbers in python

1.9k views Asked by At

I need to write a code that will find all prime numbers in a range of numbers and then list them in order saying which are prime and which are not, and also if they are not prime, show by what numbers they are divisible. It should look something like this:

>>> Prime(1,10)
1 is not a prime number 
2 is a prime number
3 is a prime number
4 is divisible by 2
5 is a prime number
6 is divisible by 2, 3
7 is a prime number
8 is divisible by 2, 4
9 is divisible by 3

so far I have this which will only identify what numbers are prime and print them in a list. I don't know how to do the non prime numbers and to print what numbers it is divisible by. Also I get that 1 is a prime number.

def primeNum(num1, num2):
   for num in range(num1,num2):
    prime = True
    for i in range(2,num):
        if (num%i==0):
            prime = False
    if prime:
       print (num,'is a prime number')
6

There are 6 answers

1
Dleep On

you could store the divisors for each number on a list and then print it with ", ".join(yourList)

i.e:

def primeNum(num1, num2):
   for num in range(num1,num2):
       divisors = []
       for i in range(2,num):
           if (num%i == 0):
               divisors.append(str(i))
       if divisors:
           print ('%d is divisible by ' %num + ', '.join(divisors))
       else:
           print ('%d is a prime number' %num)

Edit: dumb syntax error

0
Joonazan On

Just add a print and a break at the position where you set prime to false.

A more elegant solution would be to make a separate function isPrime or to use break and else in the inner for loop. Either way would make prime unnecessary.

You can only divide one by one and itself so it is a prime number, by that definition at least.

0
James Mills On

Using a sieve will do the trick:

Example:

from __future__ import print_function


def primes():
    """Prime Number Generator

    Generator an infinite sequence of primes

    http://stackoverflow.com/questions/567222/simple-prime-generator-in-python
    """

    # Maps composites to primes witnessing their compositeness.
    # This is memory efficient, as the sieve is not "run forward"
    # indefinitely, but only as long as required by the current
    # number being tested.
    #
    D = {}  

    # The running integer that's checked for primeness
    q = 2  

    while True:
        if q not in D:
            # q is a new prime.
            # Yield it and mark its first multiple that isn't
            # already marked in previous iterations
            # 
            yield q        
            D[q * q] = [q]
        else:
            # q is composite. D[q] is the list of primes that
            # divide it. Since we've reached q, we no longer
            # need it in the map, but we'll mark the next 
            # multiples of its witnesses to prepare for larger
            # numbers
            # 
            for p in D[q]:
                D.setdefault(p + q, []).append(p)
            del D[q]

        q += 1


def factors(n):
    yield 1
    i = 2
    limit = n**0.5
    while i <= limit:
        if n % i == 0:
            yield i
            n = n / i
            limit = n**0.5
        else:
            i += 1
    if n > 1:
        yield n


def primerange(start, stop):
    pg = primes()
    p = next(pg)

    for i in xrange(start, stop):
        while p < i:
            p = next(pg)

        if p == i:
            print("{0} is prime".format(i))
        else:
            print("{0} is not prime and has factors: {1}".format(i, ", ".join(map(str, set(factors(i))))))

Output:

>>> primerange(1, 10)
1 is not prime and has factors: 1
2 is prime
3 is prime
4 is not prime and has factors: 1, 2
5 is prime
6 is not prime and has factors: 1, 2, 3
7 is prime
8 is not prime and has factors: 1, 2
9 is not prime and has factors: 1, 3
0
Daryush On

This piece of code receives a number from the user and determines whether it is prime or not. I can say that it is the fastest because in mathematics, to find out whether a number is prime or not, it is enough to examine the square root of that number.

import math
prime = int(input("Enter your number: "))
count = 0
sqr = int(math.sqrt(prime))
for i in range(2, sqr+1):
    if prime % i == 0:
        print("your number is not prime")
        count += 1
        break
if count == 0:
    print("your number is prime")
1
huu hiep Tran On
> # Check a number whether prime or not
a = int(input("Please your number (>1): "))
y = 2
import math
b = math.floor(math.sqrt(a)) + 1
x = True
while x:
  if a == 2:
    print(f'{a} is prime')
    x = False
  else:
    x = True
    if a %y == 0:
      print(f' {a} is not prime')
      x = False
    else:
      y = y + 1
      if y >= b:
        print(f'{a} is prime')
        x = False
      else:
        x = True
1
AudioBubble On

Here is the Simple program for the output

def isPrime(lower,upper):
    for num in range(lower,upper+1):
        if num > 1:
            for i in range(2,num):
                if (num % 1) == 0:
                    break
            else:
                print(num," is a prime number")

def isDivisible(lower,upper):
     for num in range(lower,upper+1):
        if num > 1:
            for i in range(2,num):
                if (num % i) == 0:
                    print(num," is divisible by ", i)
                else:
                    pass
            else:
                pass
 
Lower = int(input("Enter your Lower limit"))
Upper = int(input("Enter Your Upper Limit"))          
isPrime(Lower,Upper)
isDivisible(Lower,Upper)




**This is the output to code:**
2  is a prime number
4  is divisible by  2
6  is divisible by  2
6  is divisible by  3
8  is divisible by  2
8  is divisible by  4
9  is divisible by  3
10  is divisible by  2
10  is divisible by  5




 
  1. isPrime() function will check whether the number is prime or not
  2. isDivisible() function will check whether the number is divisible or not.