web-gelistirme-sc.com

Python'da asal sayılar dizisini yazdırma

Python programlamayı öğrenmeye çalışıyorum ve bu konuda oldukça yeniyim.

Yüzden yüze bir dizi asal sayı basarken sorun yaşıyordum. Kodumda neyin yanlış olduğunu çözemiyorum.

İşte yazdıklarım; asal sayılar yerine tüm tek sayıları yazdırır:

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

2'den n-1'e kadar olan tüm sayıları kontrol etmeniz gerekir (gerçekte sqrt (n), ama tamam, n olsun). n sayılardan herhangi biri tarafından bölünebilirse, asal değildir. Bir sayı asal ise, yazdırın.

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

Aynı çok daha kısa ve daha Pythonic yazabilirsiniz:

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

Daha önce de söylediğim gibi, bölenleri 2'den n-1'e değil, 2'den sqrt'e (n) kontrol etmek daha iyi olacaktır:

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

101 gibi küçük sayılar için farketmez, ancak 10 ** 8 için fark gerçekten büyük olacaktır.

Kontrol ettiğiniz aralığı 2'ye kadar artırarak ve yalnızca tek sayıları kontrol ederek biraz daha geliştirebilirsiniz. Gibi:

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

Düzenlendi:

İlk döngüde tek sayılar seçildiğinden, ikinci döngüde çift sayıları kontrol etmenize gerek kalmaz, böylece 'i' değeri 3 ile başlayabilir ve 2 ile atlanabilir.

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
43
Igor Chubin

break şu anda içinde olduğu döngüyü sona erdirir. Dolayısıyla, yalnızca 2 ile bölünebilir olup olmadığını kontrol ederek tüm tuhaf sayıları verirsiniz. 

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

söylendiği gibi, python içinde asalları bulmak için bundan daha iyi yollar vardır.

for num in range(2,101):
    if is_prime(num):
        print(num)

def is_prime(n):
    for i in range(2, int(math.sqrt(n)) + 1):
        if n % i == 0:
            return False
    return True
11
Rob Wagner

Deneme bölünmesi yerine, Yunan matematikçi Eratosthenes'in iki bin yıldan uzun bir süre önce icat ettiği daha iyi bir yaklaşım, defalarca prime katları dökerek elek yapmaktır. 

İstenen maksimum 2 n'den 2 ile tüm sayıların bir listesini yaparak başlayın. Ardından art arda en küçük çapraz numarayı alın ve tüm katlarını çarpın; Çapraz kalmayan sayılar asaldır. 

Örneğin, 30'dan küçük sayıları dikkate alın. İlk olarak 2, asal olarak tanımlanır, ardından 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28 ve 30 çarpı işareti çizilir. Sonraki 3, asal olarak tanımlanır, ardından 6, 9, 12, 15, 18, 21, 24, 27 ve 30 çarpı işareti çıkarılır. Bir sonraki üs 5, yani 10, 15, 20, 25 ve 30 çarpı işareti. Ve bunun gibi. Kalan sayılar asal: 2, 3, 5, 7, 11, 13, 17, 19, 23 ve 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

Elek için optimize edilmiş bir versiyon ayrı ayrı 2 ele alır ve sadece tek sayılara elir. Ayrıca, mevcut prime karesinin altındaki tüm kompozitler daha küçük primerler ile çarpıldığı için, iç döngü p yerine p ^ 2 ile başlayabilir ve dış döngü n'nin karekökünde durabilir. Üzerinde çalışmak için optimize edilmiş sürümünü bırakacağım.

8
user448810

Ben en iyi çözümü benimsememe ve denemenin bir kanıtıyım. Aşağıda hem @ igor-chubin hem de @ user448810 tarafından basit örnek sınıfları oluşturmak için yaptığım bazı değişiklikler var. Öncelikle, bunun harika bir bilgi olduğunu söylememe izin verin, teşekkürler çocuklar. Ancak, akıllı çözüm için @ user448810 @ 'u onaylamam gerekiyor, ki bu test şu ana kadar (en hızlı test edilenler). Size teşekkür ederim efendim! Tüm örneklerde n olarak 1 milyon (1.000.000) değer kullanıyorum. 

Lütfen kodu denemek için çekinmeyin. 

İyi şanslar!

Metot 1 Igor Chubin tarafından tarif edildiği gibi:

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

Benchmark: 272+ saniyeden fazla

Metot 2 Igor Chubin tarafından tarif edildiği gibi:

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

Benchmark: 73.3420000076 saniye

Metod 3 Igor Chubin tarafından tarif edildiği gibi:

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

Benchmark: 11.3580000401 saniye

Metot 4 Igor Chubin tarafından tarif edildiği gibi:

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

Benchmark: 8.7009999752 saniye

Metot 5 user448810 tarafından tarif edildiği gibi (ki oldukça zekice olduğunu düşündüm):

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 saniye

Notlar: Yukarıda listelenen 5. Çözüm (user448810 tarafından önerildiği gibi) en hızlı ve en dürüst sessiz yaratıcı ve zekice olduğu ortaya çıktı. Onu seviyorum. Teşekkürler beyler!!

EDIT: Oh, ve bu arada, matematik kütüphanesini bir değerin karekökü için eşdeğer olduğu için ithal etmeye gerek olmadığını düşündüm (n **. 5). Aksi taktirde çok fazla düzenleme yapmadım, sonra değerler depolanıp çıktı dizisinin sınıf tarafından döndürülmesini sağladım. Ayrıca, sonuçların ayrıntılı bir dosyaya kaydedilmesi muhtemelen biraz daha etkili olacak ve eğer bir kerede bir tane olsaydı, ancak disk yazma nedeniyle biraz daha fazla zaman alacağı için çok fazla tasarruf sağlayabilirdi. Bence her zaman iyileştirmeye yer var. Bu yüzden umarım kod mantıklı adamlar.

4
jacktrader

1'inci N asal sayılarını döndüren bir Python Program işlevi modülü:

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
2
M.K.DHEERAJ

Yukarıdaki sorunu çözmenin en iyi yolu "Miller Rabin Primality Test" algoritmasını kullanmak olacaktır. Bir sayının asal olup olmadığını bulmak için olasılıksal bir yaklaşım kullanır. Ve aynı şey için rastladığım en etkili algoritma.

Aynı python uygulaması aşağıda gösterilmiştir:

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
2
Azharullah Shariff

Çok fazla sorun yaşamadan giriş numarasına listeleme yöntemim, asalların toplamı ile asal olmayan herhangi bir sayı alabileceğiniz özelliği kullanmaktır.

Bu nedenle, eğer giriş numarasını altındaki tüm asallarla bölerseniz ve herhangi biri tarafından eşit olarak bölünemezse, bir asalınız olduğunu bilirsiniz.

Elbette daha hızlı bir şekilde asal sayıları almanın daha hızlı yolları var, ama bu zaten çok iyi bir performans sergiliyor, çünkü özellikle giriş numarasını herhangi bir sayıya bölmüyorsunuz, ama sadece tam olarak bu sayıları tam olarak bu sayıya bölüyorsunuz.

Bu kodla bilgisayarımda 100 000'e kadar olan tüm astarları 4 saniyeden daha kısa sürede listeleyebildim. 

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)
1
user3604362
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
0
Gurvinder Singh
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)
0
Shwetank

İşte bir RECURSIVE işlevinde birinci sınıf olup olmadığını kontrol etmenin basit ve sezgisel bir versiyonu! :) (MIT sınıfı için ev ödevi olarak yaptım) Python'da 1900’e kadar çok hızlı çalışıyor. 1900’den fazla denerseniz, ilginç bir hatayla karşılaşacaksınız :) (u Bilgisayarınızın kaç sayı yönetebileceğini kontrol etmek ister misiniz?)

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

Elbette ... özyinelemeli işlevlerden hoşlanıyorsanız, bu küçük kod performansını ciddi şekilde artıracak bir sözlükle yükseltilebilir ve bu komik hatayı önlemek için .. __ İşte MEMORY entegrasyonuyla basit bir Level 1 yükseltmesi:

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"

İşte bulunan son 100 asal sayıyı bastırdığım resuls'lar.

saat ve tarih: 2013-10-15 13: 32: 11.674448

100000 yılına kadar 9594 asal sayı vardır

[99.991, 99.989, 99.971, 99.961, 99929, 99.923, 99.907, 99901, 99.881, 99.877, 99.871, 99.859, 99.839, 99833, 99829, 99.823, 99817, 99.809, 99.793, 99787, 99.767, 99761, 99.733, 99.721, 99.719 , 99713, 99709, 99.707, 99689, 99.679, 99667, 99661, 99.643, 99.623, 99611, 99.607, 99.581, 99577, 99571, 99.563, 99559, 99.551, 99.529, 99.527, 99.523, 99.497, 99.487, 99.469, 99.439, 99.431 , 99.409, 99401, 99.397, 99.391, 99.377, 99.371, 99.367, 99.349, 99347, 99.317, 99.289, 99.277, 99.259, 99.257, 99.251, 99.241, 99.233, 99223, 99191, 99.181, 99.173, 99.149, 99.139, 99.137, 99133 , 99131, 99119, 99109, 99103, 99089, 99083, 99079, 99053, 99041, 99023, 99017, 99013, 98999, 98993, 98981, 98963, 98959, 98947, 98929; ] ...

Bilgisayarınız 0: 00: 40.871083'ü hesaplamak için aldı.

Böylece i7 dizüstü bilgisayarımın hesaplaması 40 saniye sürdü. :)

0
moldovean
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
0
Rohan Chavan

sympy kütüphanesini kullanarak asal sayılar listesi yapabiliriz

import sympy
lower=int(input("lower value:"))          #let it be 30
upper=int(input("upper value:"))          #let it be 60
l=list(sympy.primerange(lower,upper+1))   #[31,37,41,43,47,53,59]
print(l)
0
praveen nani

Yeni başlayanlar için asal sayılar elde etmenin en basit mantığı:

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
0

Bu, bir sayının asal olup olmadığını kontrol etmek için yazdığım örnek bir programdır. 

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
0
Rish

Buna ne dersin? Kullandığım tüm önerileri okumak:

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’e kadar asal sayılar

[email protected]:/pywork# time python prime.py

78498 

gerçek 0m6.600'ler

kullanıcı 0m6.532'ler

sys 0m0.036s

0
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)
0
Sush Kudari

İlk önce bu sayının faktörünü bulduk

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

Asal olup olmadığını kontrol etmek için komut dosyası

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

Tüm asal sayıyı n basmak için komut dosyası

def prime_list(n):
  pri_list = []
  for i in range(1,n+1):
    if prime(i)
      pri_list.append(i)
return(pri_list)
0
kamran kausar
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
0
Monica Sai

İhmal edici primerlerin en hızlı ve en iyi uygulaması:

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)
0
Eye Sun

Igor Chubin 'ın cevabı geliştirilebilir. X'in asal olup olmadığını test ederken, algoritma X'in kareköküne kadar her sayıyı kontrol etmek zorunda değildir, sadece sqrt (X) 'a kadar olan asal sayıları kontrol etmelidir. Bu nedenle, onu oluştururken asal sayıların listesine atıfta bulunulması daha verimli olabilir. Aşağıdaki işlev, b'nin altındaki tüm prim'lerin bir listesini çıkarır; bu, birkaç nedenden ötürü bir liste olarak uygundur (örneğin, primer sayısını <b bilmek istediğinizde). Sadece primerleri kontrol ederek daha yüksek sayılarda zaman kazandırır (yaklaşık 10.000'de karşılaştırın; fark keskindir). 

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
0
user2636407

Kabul edilen cevaba ek olarak, astarları saklamak için bir liste kullanarak ve üretimden sonra yazdırmak için daha fazla optimizasyon sağlanabilir.

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
0
Arif awate
# 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
0

Döngüyü çok erken sonlandırıyorsunuz. For döngüsünün gövdesindeki tüm olasılıkları test ettikten ve kırılmadan sonra, sayı asaldır. Biri asal olmadığı için 2'den başlamalısınız:

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

Daha hızlı bir çözümde, yalnızca test ettiğiniz numaranın kökünden küçük veya ona eşit olan astarlarla bölünmeye çalışırsınız. Bu, zaten bulduğun tüm asalleri hatırlayarak başarılabilir. Ek olarak, yalnızca tek sayıları test etmeniz gerekir (2 hariç). Elde edilen algoritmayı bir jeneratöre koyabilirsiniz, böylece primerleri bir kaba saklamak veya basitçe yazdırmak için kullanabilirsiniz:

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

Gördüğünüz gibi, karekökü hesaplamaya gerek yoktur, kareyi her asal sayı için saklamak ve her böleni bu sayı ile karşılaştırmak daha hızlıdır.

0
hochl

İşte daha hızlı arama süresi için yer kaplayan farklı bir yaklaşım. Bu en hızlı olabilir.

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
0
gammazero

Filtre işlevini kullanma.

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
0
user5319825
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
0
Riyas PK

Igor'dan ilham aldım ve bir liste oluşturan bir kod bloğu yaptım:

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)
0
Tortue Genial

Bunu çözmenin daha basit ve daha etkili bir yolu daha önce bulunan tüm asal sayıları saklamak ve bir sonraki sayının daha küçük asal sayılardan herhangi birinin katı olup olmadığını kontrol etmektir.

n = 1000
primes = [2]

for i in range(3, n, 2):
    if not any(i % prime == 0 for prime in primes):
        primes.append(i)

print(primes)

any öğesinin kısa devre işlevi olduğunu, diğer bir deyişle, bir truthy değeri bulunduğunda döngüyü kıracağını unutmayın.

0
Carlos Afonso

Python kullanarak n asal sayıları yazdır:

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,
0
htoniv_91