1から100までの一連の素数を印刷する際に問題が発生していました。コードの何が問題なのか理解できません。
これが私が書いたものです。素数の代わりにすべての奇数を出力します。
for num in range(1, 101):
for i in range(2, num):
if num % i == 0:
break
else:
print(num)
break
質問する
258866 次
35 に答える
72
2からn-1までのすべての数値をチェックする必要があります（実際にはsqrt（n）に対してですが、OK、nとします）。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)
あなたは同じはるかに短く、よりpythonicを書くことができます：
for num in range(2,101):
if all(num%i!=0 for i in range(2,num)):
print (num)
すでに述べたように、除数を2からn-1ではなく、2からsqrt（n）までチェックする方がよいでしょう。
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のような小さな数の場合は問題ではありませんが、10**8の場合はその差が非常に大きくなります。
チェックする範囲を2ずつ増やして、奇数のみをチェックすることで、もう少し改善できます。そのようです：
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)
編集：
最初のループでは奇数が選択されているので、2番目のループでは偶数でチェックする必要がないため、「i」の値は3から開始し、2でスキップできます。
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)
于 2012-07-23T20:31:02.860 に答える
17
試行割り法の代わりに、2000年以上前にギリシャの数学者エラトステネスによって発明されたより良いアプローチは、複数の素数を繰り返しキャストすることによってふるいにかけることです。
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つを別々に扱い、奇数だけをふるいにかけます。また、現在の素数の2乗未満のすべてのコンポジットは小さい素数で消されているため、内側のループはpではなくp ^ 2で開始でき、外側のループはnの平方根で停止できます。最適化されたバージョンは、作業用に残しておきます。
于 2012-07-23T20:57:29.580 に答える
15
break現在のループを終了します。したがって、2で割り切れるかどうかをチェックするだけで、すべて奇数になります。
for num in range(2,101):
for i in range(2,num):
if (num%i==0):
break
else:
print(num)
そうは言っても、Pythonで素数を見つけるにはこれよりもはるかに優れた方法があります。
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
于 2012-07-23T20:25:16.623 に答える
15
私は最善の解決策を想定せず、それをテストすることを支持しています。以下は、@igor-chubinと@user448810の両方によって例の単純なクラスを作成するために行ったいくつかの変更です。まず最初に、それはすべて素晴らしい情報だと言わせてください、皆さんありがとう。しかし、私は彼の巧妙な解決策について@ user448810を認めなければなりません。これは、（私がテストしたものの中で）はるかに高速であることがわかりました。だからあなたに称賛を送ります、サー！すべての例で、nとして100万（1,000,000）の値を使用します。
気軽にコードを試してみてください。
幸運を！
IgorChubinによって説明された方法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秒以上
IgorChubinによって説明されている方法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秒
IgorChubinによって説明されている方法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秒
IgorChubinによって説明されている方法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.70009999952秒
user448810によって説明されている方法5（私はかなり賢いと思いました）：
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
ベンチマーク： 1.12000012398秒
注：上記のソリューション5（user448810によって提案されたもの）は、最も速く、正直に静かなクリエイティブで賢いことがわかりました。大好きです。みんなありがとう！！
編集：ああ、ちなみに、同等のものはちょうど（n **。5）であるため、値の平方根の数学ライブラリをインポートする必要はないと感じました。それ以外の場合は、他の多くの編集を行わず、値を格納して出力配列をクラスから返すようにしました。また、結果を詳細に保存するよりもファイルに保存する方がおそらく少し効率的であり、一度に1つだけの場合はメモリを大幅に節約できますが、ディスク書き込みのために少し時間がかかります。しかし、常に改善の余地があると思います。うまくいけば、コードは理にかなっています。
2021編集：本当に長い時間が経過したことはわかっていますが、StackoverflowをCodewarsアカウントにリンクした後、戻って、この投稿にリンクされている最近蓄積されたポイントを確認しました。元のポスターで読んだものが@user448810に気付いたので、出力配列を追加する前に奇数値を除外することで、元の投稿に記載されているわずかな変更を行うことにしました。結果は、最適化と最新バージョンのPython 3.8の両方ではるかに優れたパフォーマンスであり、結果は0.723秒（以前のコード）でしたが、nに1,000,000を使用した場合は0.504秒でした。
def primes_method5(n):
out = list()
sieve = [True] * (n+1)
for p in range(2, n+1):
if (sieve[p] and sieve[p]%2==1):
out.append(p)
for i in range(p, n+1, p):
sieve[i] = False
return out
ほぼ5年後、私はもう少し知っているかもしれませんが、それでも私はPythonが大好きで、それがそんなに長いと思うのはちょっとクレイジーです。正直なところ、この投稿は少し前に作成されたように感じられます。当時、私はPythonを使用していたのは約1年だったと思います。そして、それはまだ関連しているようです。クレイジー。良い時代。
于 2016-08-23T16:18:52.980 に答える
3
上記の問題を解決する最良の方法は、「ミラーラビン素数性テスト」アルゴリズムを使用することです。確率論的アプローチを使用して、数値が素数であるかどうかを検出します。そして、これは私がこれまでに出会った中で最も効率的なアルゴリズムです。
同じもののPython実装を以下に示します。
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
于 2016-08-20T05:18:10.590 に答える
2
イゴール・チュビンの答えは改善される可能性があります。Xが素数であるかどうかをテストする場合、アルゴリズムはXの平方根までのすべての数値をチェックする必要はなく、sqrt（X）までの素数をチェックするだけで済みます。したがって、作成時に素数のリストを参照すると、より効率的になる可能性があります。以下の関数は、bの下にあるすべての素数のリストを出力します。これは、いくつかの理由でリストとして便利です（たとえば、素数<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
于 2013-07-31T03:31:54.613 に答える
2
あまり面倒なことなく素数をエントリ番号にリストする私の方法は、素数の合計で素数ではない任意の数を取得できるというプロパティを使用することです。
したがって、エントリ番号をその下のすべての素数で除算し、それらのいずれかで均等に割り切れない場合は、素数があることがわかります。
もちろん、素数を取得する方法はまだまだありますが、これはすでに非常にうまく機能しています。特に、エントリ番号を任意の数で除算しておらず、その数までの素数だけを除算しているためです。
このコードを使用して、コンピューターで管理し、4秒未満で最大100000までのすべての素数を一覧表示しました。
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)
于 2015-06-26T18:11:42.763 に答える
2
1番目のN個の素数を返すPythonプログラム関数モジュール：
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
于 2016-06-10T06:42:01.967 に答える
2
これを解決するためのより簡単で効率的な方法は、以前に見つかったすべての素数を保存し、次の数が小さい素数の倍数であるかどうかを確認することです。
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これは短絡関数であることに注意してください。つまり、真の値が見つかるとすぐにループが中断されます。
于 2018-12-19T14:34:45.103 に答える
2
sympyライブラリを使用して素数のリストを作成できます
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)
于 2019-08-21T13:31:40.077 に答える
1
これは、再帰関数の素数であるかどうかをチェックする簡単で直感的なバージョンです。:)（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
もちろん...再帰関数が好きな場合は、この小さなコードを辞書でアップグレードして、パフォーマンスを大幅に向上させ、その面白いエラーを回避することができます。これは、MEMORY統合を使用した単純なレベル1のアップグレードです。
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
100000まで、9594の素数があります
[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、98929、98927、98911、98909、98899、98897 ]..。
それを計算するのにあなたのコンピュータは0：00：40.871083かかりました
そのため、i7ラップトップが計算するのに40秒かかりました。:)
于 2013-10-15T10:43:11.097 に答える
1
# 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
于 2015-03-17T20:34:45.370 に答える
1
ループの終了が早すぎます。forループの本体ですべての可能性をテストし、壊れていない場合、その数は素数です。1つはプライムではないため、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
平方根を計算する必要がないことがわかるように、各素数の平方を格納し、各除数をこの数と比較する方が高速です。
于 2015-06-19T11:14:16.427 に答える
1
これはどう？私がこれを使用したすべての提案を読んで：
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
実数0分6.600秒
ユーザー0m6.532s
sys 0m0.036s
于 2016-09-30T09:52:17.787 に答える
1
受け入れられた回答に加えて、リストを使用して素数を格納し、生成後にそれらを印刷することで、さらに最適化を行うことができます。
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
于 2018-02-10T10:05:04.357 に答える
1
初心者が素数を取得するための最も簡単なロジックは次のとおりです。
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
于 2018-06-08T06:28:45.953 に答える
1
n = int(input())
is_prime = lambda n: all( n%i != 0 for i in range(2, int(n**.5)+1) )
def Prime_series(n):
for i in range(2,n):
if is_prime(i) == True:
print(i,end = " ")
else:
pass
Prime_series(n)
これはラムダ関数を使用した簡単な答えです。
于 2019-10-24T13:39:29.637 に答える
1
def function(number):
for j in range(2, number+1):
if all(j % i != 0 for i in range(2, j)):
print(j)
function(13)
于 2021-02-26T14:26:00.103 に答える
0
Pythonを使用してn個の素数を出力します。
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,
于 2013-07-04T16:07:49.023 に答える
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)
于 2014-09-08T00:43:03.657 に答える
0
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
于 2015-06-19T07:04:02.627 に答える
0
これは、数が素数であるかどうかを確認するために私が書いたサンプルプログラムです。
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
于 2015-06-22T19:06:54.213 に答える
0
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
于 2016-07-28T08:02:04.010 に答える
0
フィルタ機能を使用します。
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
于 2016-08-09T17:53:32.907 に答える
0
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
于 2016-08-15T17:40:56.000 に答える
0
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
于 2017-05-18T05:42:36.003 に答える
0
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
于 2017-07-11T02:28:49.707 に答える
0
素数を省略することの最速かつ最良の実装：
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)
于 2017-10-08T05:57:19.907 に答える
0
これは、検索時間を短縮するためにスペースを交換する別のアプローチです。これは最速かもしれません。
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
于 2017-10-17T21:11:56.970 に答える
0
私はIgorに触発され、リストを作成するコードブロックを作成しました。
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)
于 2018-01-26T11:46:39.587 に答える
0
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)
于 2018-07-14T16:00:21.340 に答える
0
まず、その数の因数を見つけます
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)
于 2018-07-24T18:23:25.827 に答える
0
for i in range(1, 100):
for j in range(2, i):
if i % j == 0:
break
else:
print(i)
于 2021-07-13T04:50:17.890 に答える
-1
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))
于 2018-05-06T10:06:01.170 に答える
-1
min = int（input（ "Enter lower range："））max = int（input（ "Enter upper range："））
print（ "The Prime numbes between"、min、 "and"、max、 "are："
for num in range（min、max + 1）：if num> 1：for i in range（2、num）：if（num％i）== 0：break else：print（num）
于 2018-12-19T13:31:12.027 に答える