Я хотел бы генерировать простые числа от 2 до 100 в PYTHON [duplicate]

Добавляя к принятому ответу, дальнейшая оптимизация может быть достигнута путем использования списка для хранения простых чисел и их печати после генерации.

import math
Primes_Upto = 101
Primes = [2]
for num in range(3,Primes_Upto,2):
    if all(num%i!=0 for i in Primes):
       Primes.append(num)
for i in Primes:
    print i

Самый быстрый & amp; наилучшая реализация пропусков простых чисел:

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)

Вот другой подход, который торгует пространство для более быстрого поиска. Это может быть быстрее всего.

import math

def primes(n):
    if n < 2:
        return []
    numbers = [0]*(n+1)
    primes = [2]
    # Mark all odd numbers as maybe prime, leave evens marked composite.
    for i in xrange(3, n+1, 2):
        numbers[i] = 1

    sqn = int(math.sqrt(n))
    # Starting with 3, look at each odd number.
    for i in xrange(3, len(numbers), 2):
        # Skip if composite.
        if numbers[i] == 0:
            continue
        # Number is prime.  Would have been marked as composite if there were
        # any smaller prime factors already examined.
        primes.append(i)
        if i > sqn:
            # All remaining odd numbers not marked composite must be prime.
            primes.extend([i for i in xrange(i+2, len(numbers), 2)
                           if numbers[i]])
            break
        # Mark all multiples of the prime as composite.  Check odd multiples.
        for r in xrange(i*i, len(numbers), i*2):
            numbers[r] = 0

    return primes

n = 1000000
p = primes(n)
print "Found", len(p), "primes <=", n

min=int(input("min:"))
max=int(input("max:"))
for num in range(min,max):
    for x in range(2,num):
        if(num%x==0 and num!=1):
            break
        else:
            print(num,"is prime")
            break

Вы заканчиваете цикл слишком рано. После того, как вы проверили все возможности в теле цикла for, а не сломались, число будет простым. Поскольку одно не простое, вам нужно начинать с 2:

for num in xrange(2, 101):
    for i in range(2,num):
        if not num % i:
            break
    else:
        print num

. В более быстром решении вы пытаетесь разделить на простые числа, которые меньше или равны корню числа, которое вы тестируете. Это может быть достигнуто путем запоминания всех простых чисел, которые вы уже нашли. Кроме того, вам нужно только проверить нечетные числа (кроме 2). Вы можете поместить полученный алгоритм в генератор, чтобы вы могли использовать его для хранения простых в контейнере или просто распечатывать их:

def primes(limit):
    if limit > 1:
        primes_found = [(2, 4)]
        yield 2
        for n in xrange(3, limit + 1, 2):
            for p, ps in primes_found:
                if ps > n:
                    primes_found.append((n, n * n))
                    yield n
                    break
                else:
                    if not n % p:
                        break

for i in primes(101):
    print i

Как вы можете видеть, нет необходимости вычислять квадратный корень, быстрее хранить квадрат для каждого простого числа и сравнивать каждый делитель с этим числом.

Печать n простых чисел с использованием 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,

Я сторонник того, чтобы не принимать лучшее решение и тестировать его. Ниже приведены некоторые изменения, которые я сделал для создания простых классов примеров, как с помощью @ igor-chubin, так и с @ user448810. Прежде всего позвольте мне сказать, что это отличная информация, спасибо вам, ребята. Но я должен признать @ user448810 за его умное решение, которое оказалось самым быстрым на сегодняшний день (из тех, что я тестировал). Так тебе, сэр! Во всех примерах я использую значения 1 миллион (1 000 000) в виде n.

Пожалуйста, не стесняйтесь попробовать код.

Удачи!

Метод 1, описанный Игорем Чубиным:

def primes_method1(n):
    out = list()
    for num in range(1, n+1):
        prime = True
        for i in range(2, num):
            if (num % i == 0):
                prime = False
        if prime:
            out.append(num)
    return out

Тест: более 272 секунд

Метод 2 как описано Игорем Чубиным:

def primes_method2(n):
    out = list()
    for num in range(1, n+1):
        if all(num % i != 0 for i in range(2, num)):
            out.append(num)
    return out

Контрольный показатель: 73.3420000076 секунд

Метод 3, описанный Игорем Чубиным:

def primes_method3(n):
    out = list()
    for num in range(1, n+1):
        if all(num % i != 0 for i in range(2, int(num**.5 ) + 1)):
            out.append(num)
    return out

Контрольный показатель: 11.3580000401 секунд

Метод 4, описанный Игорем Чубиным:

def primes_method4(n):
    out = list()
    out.append(2)
    for num in range(3, n+1, 2):
        if all(num % i != 0 for i in range(2, int(num**.5 ) + 1)):
            out.append(num)
    return out

Контрольный показатель: 8.7009999752 секунд

Метод 5, как описано пользователем448810 (что, по моему мнению, было довольно умно):

def primes_method5(n):
    out = list()
    sieve = [True] * (n+1)
    for p in range(2, n+1):
        if (sieve[p]):
            out.append(p)
            for i in range(p, n+1, p):
                sieve[i] = False
    return out

Benchmark: 1.12000012398 секунд

Примечания: Решение 5, указанное выше (как было предложено пользователем448810), оказалось самым быстрым и честным тихим творческим и умным. Я люблю это. Спасибо, ребята !!

EDIT: О, и, кстати, я не чувствовал необходимости импортировать математическую библиотеку для квадратного корня из значения, поскольку эквивалент просто (n ** 0,5). В противном случае я не редактировал много других, а затем возвращал значения в массив и возвращал массив. Кроме того, было бы, вероятно, немного более эффективно хранить результаты в файле, чем подробные, и могло бы сэкономить много на памяти, если бы это было просто по одному, но стоило бы немного больше времени из-за записи на диск. Я думаю, что всегда есть место для улучшения. Так что, надеюсь, код имеет смысл.

Сначала мы находим коэффициент этого числа

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

Сценарий для проверки простого или нет

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

Сценарий для печати всего простого числа до n

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

Вот простейшая логика для начинающих, чтобы получить простые числа:

p=[]
for n in range(2,50):
    for k in range(2,50):
        if n%k ==0 and n !=k:
            break
        else:
            for t in p:
                if  n%t ==0:
                    break
            else:
                p.append(n)

print p

Вот простая и интуитивно понятная версия проверки, является ли это простым в функции RECURSIVE! :) (Я сделал это как домашнее задание для класса MIT). В python он работает очень быстро до 1900 года. Если вы попробуете более 1900, вы получите интересную ошибку :) (Хотелось бы проверить, сколько номеров компьютер может управлять?)

def is_prime(n, div=2):

    if div> n/2.0: return True

    if n% div == 0:
        return False
    else:
        div+=1
        return is_prime(n,div)

#The program:
until = 1000
for i in range(until):
    if is_prime(i):
        print i

Конечно ... если вам нравятся рекурсивные функции, этот маленький код может быть обновлен со словарем, чтобы серьезно увеличить его производительность и избежать этой смешной ошибки. Вот простой вариант обновления 1 уровня с интеграцией MEMORY:

import datetime
def is_prime(n, div=2):
    global primelist
    if div> n/2.0: return True
    if div < primelist[0]:
        div = primelist[0]
        for x in primelist:
            if x ==0 or x==1: continue
            if n % x == 0:
                return False
    if n% div == 0:
        return False
    else:
        div+=1
        return is_prime(n,div)


now = datetime.datetime.now()
print 'time and date:',now
until = 100000
primelist=[]
for i in range(until):
    if is_prime(i):
        primelist.insert(0,i)
print "There are", len(primelist),"prime numbers, until", until
print primelist[0:100], "..."

finish = datetime.datetime.now()
print "It took your computer", finish - now , " to calculate it"

Вот резули, где я напечатал последние 100 простых чисел.

время и дата: 2013-10-15 13: 32: 11.674448

Имеются 9594 простых чисел, до 100000

[99991, 99989, 99971, 99961, 99929, 99923, 99907, 99901, 99881, 99877, 99871, 99859, 99839, 99833, 99829, 99823, 99817, 99809, 99793, 99787, 99767, 99761, 99733, 99721, 99719 , 99713, 99709, 99707, 99689, 99679, 99667, 99661, 99643, 99623, 99611, 99607, 99581, 99577, 99571, 99563, 99559, 99551, 99529, 99527, 99523, 99497, 99487, 99469, 99439, 99431 , 99409, 99401, 99397, 99391, 99377, 99371, 99367, 99349, 99347, 99317, 99289, 99277, 99259, 99257, 99251, 99241, 99233, 99223, 99191, 99181, 99173, 99149, 99139, 99137, 99133 , 99131, 99119, 99109, 99103, 99089, 99083, 99079, 99053, 99041, 99023, 99017, 99013, 98999, 98993, 98981, 98963, 98953, 98947, 98939, 9892 9, 98927, 98911, 98909, 98899, 98897] ...

Для его вычисления потребовался ваш компьютер 0: 00: 40.871083

Так что для моего ноутбука i7 потребовалось 40 секунд для его расчета. :)

f=0
sum=0
for i in range(1,101):
    for j in range(1,i+1):
        if(i%j==0):
            f=f+1
    if(f==2):
        sum=sum+i
        print i        
    f=0
print sum

Это пример программы, которую я написал, чтобы проверить, является ли число простым или нет.

def is_prime(x):
    y=0
    if x<=1:
        return False
    elif x == 2:
        return True
    elif x%2==0:
        return False
    else:
        root = int(x**.5)+2
        for i in xrange (2,root):
            if x%i==0:
                return False
                y=1
        if y==0:
            return True

Добавление моей собственной версии, просто чтобы показать некоторые трюки itertools v2.7:

import itertools

def Primes():
    primes = []
    a = 2
    while True:
        if all(itertools.imap(lambda p : a % p, primes)):
            yield a
            primes.append(a)
        a += 1

# Print the first 100 primes
for _, p in itertools.izip(xrange(100), Primes()):
    print p

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

n = int(raw_input('Enter the integer range to find prime no :'))
p = 2
while p<n:
  i = p
  cnt = 0
  while i>1:
    if p%i == 0:
        cnt+=1
    i-=1
  if cnt == 1:
     print "%s is Prime Number"%p
  else:
     print "%s is Not Prime Number"%p
  p+=1

a=int(input('enter the lower no.'))
b=int(input('enter the higher no.'))
print("Prime numbers between",a,"and",b,"are:")
for num in range(a,b):

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

# computes first n prime numbers
def primes(n=1):
    from math import sqrt
    count = 1
    plist = [2]
    c = 3
    if n <= 0 :
        return "Error : integer n not >= 0"
    while (count <= n - 1):    # n - 1 since 2 is already in plist
        pivot = int(sqrt(c))
        for i in plist:
            if i > pivot :    # check for primae factors 'till sqrt c
                count+= 1
                plist.append(c)
                break
            elif c % i == 0 :
                break    # not prime, no need to iterate anymore
            else :
                continue 
        c += 2    # skipping even numbers              
    return plist

num= int(input("Enter the numbner"))
isDivisible= False
int=2

while i<num:
    if num%i==0
    isDivisible True
    print("The number {} is divisible by {}.".format(num,i))
    i +=1

if isDivisible:
    print("The number {} is not prime.".format(num))
else:
    print("The number {} is a prime number.".format(num))

def prime_number(a):
    yes=[]
    for i in range (2,100):
        if (i==2 or i==3 or i==5 or i==7) or (i%2!=0 and i%3!=0 and i%5!=0 and i%7!=0 and i%(i**(float(0.5)))!=0):
            yes=yes+[i]
    print (yes)

Я был вдохновлен Игорем и сделал блок кода, который создает список:

def prime_number():

for num in range(2, 101):
    prime = True
    for i in range(2, num):
        if (num % i == 0):
            prime = False
    if prime and num not in num_list:
        num_list.append(num)
    else:
        pass
return num_list


num_list = []
prime_number()
print(num_list)

Как насчет этого? Чтение всех предложений, которые я использовал:

prime=[2]+[num for num in xrange(3,m+1,2) if all(num%i!=0 for i in range(2,int(math.sqrt(num))+1))]

Основные номера до 1000000

root@nfs:/pywork# time python prime.py

78498

real 0m6.600s

пользователь 0m6.532s

sys 0m0.036s

Ответ Игоря Чубина можно улучшить. При тестировании, если X является простым, алгоритм не должен проверять каждое число до квадратного корня из X, он должен проверять только простые числа до sqrt (X). Таким образом, он может быть более эффективным, если он ссылается на список простых чисел по мере его создания. Функция ниже выводит список всех простых чисел под b, что удобно в виде списка по нескольким причинам (например, когда вы хотите узнать количество простых чисел & lt; b). Проверяя простые числа, он экономит время при более высоких числах (сравните около 10 000, разница резко).

from math import sqrt
def lp(b)
    primes = [2]
    for c in range(3,b):
        e = round(sqrt(c)) + 1
        for d in primes:
            if d <= e and c%d == 0:
                break
        else:
            primes.extend([c])
    return primes

Мой способ перечисления простых чисел на номер записи без лишних хлопот заключается в использовании свойства, которое вы можете получить любым числом, которое не является простым с суммированием простых чисел.

Поэтому, если вы разделите номер входа со всеми штрихами ниже него, и он нигде не делится ни на один из них, вы знаете, что у вас есть премьер.

Конечно, есть еще более быстрые способы получения простых чисел, но этот уже выполняется очень хорошо, особенно потому, что вы не делите номер записи на любое число, а достаточно всего простых чисел до этого числа.

С помощью этого кода мне удалось на моем компьютере перечислить все простые числа до 100 000 менее чем за 4 секунды.

import time as t

start = t.clock()

primes = [2,3,5,7]

for num in xrange(3,100000,2):
    if all(num%x != 0 for x in primes):
        primes.append(num)

print primes
print t.clock() - start
print sum(primes)

Вместо пробного разделения лучший подход, изобретенный греческим математиком Эратосфеном более двух тысяч лет назад, состоит в том, чтобы просеять, многократно изгоняя кратные простые числа.

Начните с составления списка всех чисел от 2 до максимального желаемого числа n. Затем многократно принимайте наименьшее непересекающееся число и вычеркивайте все его кратные числа; числа, которые остаются непересекающимися, являются просторными.

Например, рассмотрите числа, меньшие 30. Сначала 2 идентифицируется как простой, затем 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28 и 30 вычеркнуты. Следующие 3 обозначены как простые, затем 6, 9, 12, 15, 18, 21, 24, 27 и 30 вычеркнуты. Следующий штрих равен 5, поэтому 10, 15, 20, 25 и 30 вычеркнуты. И так далее. Цифры остаются неизменными: 2, 3, 5, 7, 11, 13, 17, 19, 23 и 29.

def primes(n):
  sieve = [True] * (n+1)
  for p in range(2, n+1):
    if (sieve[p]):
      print p
      for i in range(p, n+1, p):
        sieve[i] = False

Оптимизированная версия сита обрабатывает 2 отдельно и сита только нечетные числа. Кроме того, поскольку все композиты, меньшие квадрата текущего штриха, пересекаются меньшими штрихами, внутренний цикл может начинаться с p ^ 2 вместо p, а внешний цикл может останавливаться у квадратного корня n. Я оставлю оптимизированную версию для вас.

Использование функции фильтра.

l=range(1,101)
for i in range(2,10): # for i in range(x,y), here y should be around or <= sqrt(101)
    l = filter(lambda x: x==i or x%i, l)

print l