私はプログラミングの世界に不慣れです。N個の素数を生成するためにPythonでこのコードを書いていました。ユーザーは、出力する素数の総数である N の値を入力する必要があります。このコードを書きましたが、目的の出力がスローされません。代わりに、N 番目の数まで素数を出力します。
例: ユーザーは N = 7 の値を入力します。
望ましい出力: 2、3、5、7、11、13、19
実際の出力: 2、3、5、7
親切なアドバイス。
i = 1
x = int(input("Enter the number:"))
for k in range(1, x+1):
c = 0
for j in range(1, i+1):
a = i % j
if a == 0:
c = c + 1
if c == 2:
print(i)
else:
k = k - 1
i = i + 1
正規表現の使用:)
#!/usr/bin/python
import re, sys
def isPrime(n):
# see http://www.noulakaz.net/weblog/2007/03/18/a-regular-expression-to-check-for-prime-numbers/
return re.match(r'^1?$|^(11+?)\1+$', '1' * n) == None
N = int(sys.argv[1]) # number of primes wanted (from command-line)
M = 100 # upper-bound of search space
l = list() # result list
while len(l) < N:
l += filter(isPrime, range(M - 100, M)) # append prime element of [M - 100, M] to l
M += 100 # increment upper-bound
print l[:N] # print result list limited to N elements
参考までに、記載されているさまざまなソリューションの間にはかなり大きな速度の違いがあります。ここにいくつかの比較コードがあります。Lennart が指摘する解決策は「historic」と呼ばれ、Ants が提案するものは「naive」と呼ばれ、RC が提案するものは「regexp」と呼ばれます。
from sys import argv
from time import time
def prime(i, primes):
for prime in primes:
if not (i == prime or i % prime):
return False
primes.add(i)
return i
def historic(n):
primes = set([2])
i, p = 2, 0
while True:
if prime(i, primes):
p += 1
if p == n:
return primes
i += 1
def naive(n):
from itertools import count, islice
primes = (n for n in count(2) if all(n % d for d in range(2, n)))
return islice(primes, 0, n)
def isPrime(n):
import re
# see http://tinyurl.com/3dbhjv
return re.match(r'^1?$|^(11+?)\1+$', '1' * n) == None
def regexp(n):
import sys
N = int(sys.argv[1]) # number of primes wanted (from command-line)
M = 100 # upper-bound of search space
l = list() # result list
while len(l) < N:
l += filter(isPrime, range(M - 100, M)) # append prime element of [M - 100, M] to l
M += 100 # increment upper-bound
return l[:N] # print result list limited to N elements
def dotime(func, n):
print func.__name__
start = time()
print sorted(list(func(n)))
print 'Time in seconds: ' + str(time() - start)
if __name__ == "__main__":
for func in naive, historic, regexp:
dotime(func, int(argv[1]))
私のマシンでの n = 100 の出力は次のとおりです。
naive
[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, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509, 521, 523, 541]
Time in seconds: 0.0219371318817
historic
[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, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509, 521, 523, 541]
Time in seconds: 0.00515413284302
regexp
[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, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509, 521, 523, 541]
Time in seconds: 0.0733318328857
ご覧のとおり、かなり大きな違いがあります。これも 1000 の場合です (主な出力は削除されています)。
naive
Time in seconds: 1.49018788338
historic
Time in seconds: 0.148319005966
regexp
Time in seconds: 29.2350409031
David Eppsteinによる超高速ふるいの実装- 私の PC では最初の 1000 個の素数に 0.146 秒かかります。
def gen_primes():
""" Generate an infinite sequence of prime numbers.
"""
# 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
primes = gen_primes()
x = set()
y = 0
a = gen_primes()
while y < 10000:
x |= set([a.next()])
y+=1
print "x contains {:,d} primes".format(len(x))
print "largest is {:,d}".format(sorted(x)[-1])
ラインk = k-1はあなたが思うことをしません。効果はありません。変更kしてもループには影響しません。反復ごとkに範囲の次の要素に割り当てられるためk、ループ内で行った変更はすべて上書きされます。
あなたが望むのは次のようなものです：
x = int(input("Enter the number:"))
count = 0
num = 2
while count < x:
if isnumprime(x):
print(x)
count += 1
num += 1
実装はあなたに任せますisnumprime();) ヒント: 以前に見つかったすべての素数で除算をテストするだけで済みます。
最初のn個の素数を出力するために最終的に思いついたのは次のとおりです。
numprimes = raw_input('How many primes to print? ')
count = 0
potentialprime = 2
def primetest(potentialprime):
divisor = 2
while divisor <= potentialprime:
if potentialprime == 2:
return True
elif potentialprime % divisor == 0:
return False
while potentialprime % divisor != 0:
if potentialprime - divisor > 1:
divisor += 1
else:
return True
while count < int(numprimes):
if primetest(potentialprime) == True:
print 'Prime #' + str(count + 1), 'is', potentialprime
count += 1
potentialprime += 1
N 個の素数が得られるまで、自然数を 1 つずつ取り、これまでに収集した素数のいずれかがそれを割るかどうかを確認します。
誰もそうしない場合は、「イェーイ」、新しい素数があります...
それでおしまい。
>>> def generate_n_primes(N):
... primes = []
... chkthis = 2
... while len(primes) < N:
... ptest = [chkthis for i in primes if chkthis%i == 0]
... primes += [] if ptest else [chkthis]
... chkthis += 1
... return primes
...
>>> print generate_n_primes(15)
[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47]
ジェネレータ式を使用して、すべての素数のシーケンスを作成し、その 100 番目をスライスします。
from itertools import count, islice
primes = (n for n in count(2) if all(n % d for d in range(2, n)))
print("100th prime is %d" % next(islice(primes, 99, 100)))
素数入力の数を取ることができます。あなたの方法に従って、ここでは事前定義された10のカウントを取得しました：
i = 2
if i == 2:
print(str(i) + "is a prime no")
i = i+1
c=1
while c<10:
for j in range(2, i):
if i%j==0:
break
if i == j+1:
print(str(i) + "is aa prime no")
c=c+1
i=i+1
これは役立つかもしれません：
import sys
from time import time
def prime(N):
M=100
l=[]
while len(l) < N:
for i in range(M-100,M):
num = filter(lambda y :i % y == 0,(y for y in range(2 ,(i/2))))
if not num and i not in [0,1,4]:
l.append(i)
M +=100
return l[:N]
def dotime(func, n):
print func.__name__
start = time()
print sorted(list(func(n))),len(list(func(n)))
print 'Time in seconds: ' + str(time() - start)
if __name__ == "__main__":
dotime(prime, int(sys.argv[1]))
Python V3 で素数をいじっているときに、複合 (非素数) 数を割り切れる最小の数は、それ自体が常に、テスト対象の数の平方根より小さい素数であることに気付きました。
以下は、最初の N 個の素数を計算するためのその発見の実装です。
0.028 秒で最初の 1,000 個の素数 | 0.6 秒で最初の 10,000 個の素数 | 14.3S で最初の 100,000 個の素数
以下のスニペットは、生成にかかった時間も示しており、素数を適切な表形式で出力しています。
import time
import math
def first_n_Primes(n):
number_under_test = 4
primes = [2,3]
while len(primes) < n:
check = False
for prime in primes:
if prime > math.sqrt(number_under_test) : break
if number_under_test % prime == 0:
check = True
break
if not check:
for counter in range(primes[len(primes)-1],number_under_test-1,2):
if number_under_test % counter == 0:
check = True
break
if not check:
primes.append(number_under_test)
number_under_test+=1
return primes
start_time = time.time()
data = first_n_Primes(1000)
end_time = time.time()
i = 1
while i < len(data)+1:
print('{0: <9}'.format(str(data[i-1])), end="")
if i%10 == 0: print("")
i+=1
print("\nFirst %d primes took %s seconds ---" % (len(data),end_time - start_time))
while ループを使用してカウントを確認してみてください。これは簡単です。以下のコード スニペットを見つけます。
i=1
count = 0;
x = int(input("Enter the number:\n"))
while (count < x):
c=0
for j in range (1, (i+1), 1):
a = i%j
if (a==0):
c = c+1
if (c==2):
print (i)
count = count+1
i=i+1
このコードは非常に混乱しており、コードを書いたときに何を考えていたのか、何を達成しようとしていたのか正確にはわかりません。コーディング方法を理解しようとするときに最初に提案することは、変数名を非常にわかりやすいものにすることから始めることです。これは、自分がやっていることのアイデアを頭の中でまっすぐに理解するのに役立ちます。また、あなたのアイデアをまっすぐに理解する方法をあなたに教えようとしている人にも役立ちます。
そうは言っても、目標に近いことを達成するサンプルプログラムは次のとおりです。
primewanted = int(input("This program will give you the nth prime.\nPlease enter n:"))
if primewanted <= 0:
print "n must be >= 1"
else:
lastprime = 2 # 2 is the very first prime number
primesfound = 1 # Since 2 is the very first prime, we've found 1 prime
possibleprime = lastprime + 1 # Start search for new primes right after
while primesfound < primewanted:
# Start at 2. Things divisible by 1 might still be prime
testdivisor = 2
# Something is still possibly prime if it divided with a remainder.
still_possibly_prime = ((possibleprime % testdivisor) != 0)
# (testdivisor + 1) because we never want to divide a number by itself.
while still_possibly_prime and ((testdivisor + 1) < possibleprime):
testdivisor = testdivisor + 1
still_possibly_prime = ((possibleprime % testdivisor) != 0)
# If after all that looping the prime is still possibly prime,
# then it is prime.
if still_possibly_prime:
lastprime = possibleprime
primesfound = primesfound + 1
# Go on ahead to see if the next number is prime
possibleprime = possibleprime + 1
print "This nth prime is:", lastprime
このコードのビット:
testdivisor = 2
# Something is still possibly prime if it divided with a remainder.
still_possibly_prime = ((possibleprime % testdivisor) != 0)
# (testdivisor + 1) because we never want to divide a number by itself.
while still_possibly_prime and ((testdivisor + 1) < possibleprime):
testdivisor = testdivisor + 1
still_possibly_prime = ((possibleprime % testdivisor) != 0)
やや遅いが、おそらくより理解しやすいものに置き換えることができます。
# Assume the number is prime until we prove otherwise
still_possibly_prime = True
# Start at 2. Things divisible by 1 might still be prime
for testdivisor in xrange(2, possibleprime, 1):
# Something is still possibly prime if it divided with a
# remainder. And if it is ever found to be not prime, it's not
# prime, so never check again.
if still_possibly_prime:
still_possibly_prime = ((possibleprime % testdivisor) != 0)
count = -1
n = int(raw_input("how many primes you want starting from 2 "))
primes=[[]]*n
for p in range(2, n**2):
for i in range(2, p):
if p % i == 0:
break
else:
count +=1
primes[count]= p
if count == n-1:
break
print (primes)
print 'Done'
これを試して：
primeList = []
for num in range(2,10000):
if all(num%i!=0 for i in range(2,num)):
primeList.append(num)
x = int(raw_input("Enter n: "))
for i in range(x):
print primeList[i]
これは私のバージョンです
import timeit
import math
__author__ = 'rain'
primes = [2]
def is_prime(n):
for prime in primes:
if n % prime == 0:
return False
return True
def find_nth_prime(n):
current_index = 0
while(len(primes) < n):
if current_index == 0:
start_value = 3
end_value = 2 * 2
else:
start_value = primes[current_index - 1] * primes[current_index - 1] + 1
end_value = primes[current_index] * primes[current_index]
for i in range(start_value, end_value):
if is_prime(i):
primes.append(i)
current_index += 1
return primes[n-1]
def solve():
return find_nth_prime(10001)
print solve()
print timeit.timeit(solve, number=10)
私はふるいを使って素数をスキャンします。とても速いです
10001 番目の素数 (10 回) を取得するのに 3.8e-06 秒しかかかりません。
n=int(input("Enter the number:: "))
for i in range(2,n):
p=i
k=0
for j in range(2,p-1):
if(p%j==0):
k=k+1
if(k==0):
print(p)
これは役立つかもしれません：
def in_prime(n):
p=True
i=2
if i**2<=n:
if n%i==0:
p=False
break
if (p):
return n
私はPythonに慣れていないので、Cのカウンター部分を書いています（疑似コードを書くのが面倒です.. :P）最初のn個の素数を見つけるには.. //すべての素数を出力します..わざわざ配列を作成して返すなど。
void find_first_n_primes(int n){
int count = 0;
for(int i=2;count<=n;i++){
factFlag == 0; //flag for factor count...
for(int k=2;k<sqrt(n)+1;k++){
if(i%k == 0) // factor found..
factFlag++;
}
if(factFlag==0)// no factors found hence prime..
{
Print(i); // prime displayed..
count++;
}
}
}
n=1
c=0
while n>0:
for i in range(2,n):
if n%i == 0:
break
else:
print(n,'is a prime')
c=c+1
n=n+1
if c==1000:
break