1樓：藍冰
要求不高的話，就用2、3、6篩選。
對於1,2,3三個數字特殊處理
所有的素數都在6的倍數的左側或者右側，也即num % 6 == 1 || num % 6 == 5，不滿足者不是素數，滿足者繼續驗證
計算sqrt(num)，從5,11,17,23...開始驗證，每次驗證i和i+2，一旦整除，不是素數
多次篩的時候可以打表。
解釋一下打表。
比如說，求乙個陣列中，任意兩個數字之和為素數的個數。在陣列非常大的時候，我們很可能重複判定某些數字是否是素數，比如1781+3280和1780+3281，同樣乙個數字我們卻判斷了很多次。所以可以先把0~10000的數字是否是素數全部計算後儲存下來。
具體做法就是定義乙個長度為10000的陣列a[10000]，對每乙個a[i]初始化為0（非素數）或1（素數）。
這樣要想知道1781+3280=5061是否為素數，直接看a[5061]是0還是1就行了，而不需要重複計算。
高階一點，Google一下「尤拉篩法」。
2樓：hresh
質數又稱素數。指在乙個大於1的自然數中，除了1和此整數自身外，不能被其他自然數整除的數。素數在數論中有著很重要的地位。
比 1 大但不是素數的數稱為合數。1 和 0 既非素數也非合數，2 是素數。
1.判斷是否是素數：
import
timeit
from
math
import
sqrt
defisPrimes1(n
):if
n<=1:
return
False
fori
inrange(2
,int
(sqrt(n
)+1)):ifn
%i==0
:return
False
return
True
defisPrimes2(n
):if
n>1:
ifn==2
:return
Trueifn
%2==0
:return
False
forx
inrange(3
,int
(sqrt(n
)+1),
2):ifn
%x==0
:return
False
return
True
return
False
(timeit
.timeit
("isPrimes1(100)"
,setup
="from chapter01 import isPrimes1"
,number
=10000
(timeit
.timeit
("isPrimes2(100)"
,setup
="from chapter01 import isPrimes2"
,number
=10000
))0.00563765699999999
0.001561703999999997
後一種方法將除 2 之外的偶數排除，大大減少了執行時間。
2.求 n 以內的素數
import
timeit
from
math
import
sqrt
import
copy
deflistPrimes1(n
):"""
初始所有乙個n維陣列 res 表示數都為素數。
從3開始將3的奇數倍標記成False，即不是素數。
之後對每乙個素數此行上一步操作
這裡我們不用管偶數倍，因為我們最後判定時預設所有偶數不是素數
"""if
n<3:
ifn==2
:return[2
]return
None
res=
[True]*
nforiin
range(3
,int(n
**0.5)+
1,2):
res[i*
i::2*
i]=[
False]*
((n-i
*i-1
)//(2
*i)+
1)return[2
]+[i
fori
inrange(3
,n,2
)ifres[i]]
deflistPrimes2(n
):'''
計算n之內的素數
:param n:
:return:
'''if
n<3:
ifn==2
:return[2
]return
None
num_list=[
xforxin
range(2
,n)if
x%2!=
0]new_list
=copy
.copy
(num_list
)# new_list =
fori
innum_list
:fordin
range(3
,int
(sqrt(i
))+1,
2):ifi
%d==0
:new_list
.remove(i
)break
return[2
]+new_list
deflistPrimes3(n
):'''
計算n之內的素數
:param n:
:return:
'''if
n<3:
ifn==2
:return[2
]return
None
return[2
]+[p
forp
inrange(2
,n)if
p%2!=
0and
0notin[
p%dfordin
range(2
,int
(sqrt(p
))+1)]]
(timeit
.timeit
("listPrimes1(100)"
,setup
="from chapter01 import listPrimes1"
,number
=100
(timeit
.timeit
("listPrimes2(100)"
,setup
="from chapter01 import listPrimes2"
,number
=100
(timeit
.timeit
("listPrimes3(100)"
,setup
="from chapter01 import listPrimes3"
,number
=100
))整理得到三種實現方法，其中第一種方法執行時間最短。
0.000947919999999991
0.003774201000000005
0.004751936999999984
3.求 m 到 n 之間的素數
defmnPrimes1(m
,n):ifm==
1:num_list=[
2]+[
pforpin
range(2
,n)if
p%2!=
0and
0notin[
p%dfordin
range(2
,int
(sqrt(p
))+1)]]ifm
>=2:
num_list=[
pforpin
range(m
,n)if
p%2!=
0and
0notin[
p%dfordin
range(2
,int
(sqrt(p
))+1)]]
return
num_list
defmnPrimes2(m
,n):num_list=[
xforxin
range(m
,n)if
x%2!=
0andx!=
1]new_list
=copy
.copy
(num_list
)foriin
num_list
:fordin
range(3
,int
(sqrt(i
))+1,
2):ifi
%d==0
:new_list
.remove(i
)breakifm
==2:new_list=[
2]+new_list
return
new_list
3樓：魯智深
#coding=utf-8
#函式用於判斷某乙個數是不是素數
deftest
(num
):list=
#定義列表，用於儲存計算i=
num-
1#去除本身
while
i>1:
#去除1
ifnum%i
==0:#判斷是否有餘數
list.(
i)#將所以有的能整除它數加入列表i-=
1iflen(
list)==
0:#如果列表為空，就是表示除了1個它本身能整除print
(num
,end
=" "
)#此函式用於判斷計算出需要判斷的所有數字100～200deftest2
(star_num
,and_num):j
=star_num
while
j :test(j )j+=1 test2 (100 ,200 )print("" )方法有很多，此方法是while迴圈操作 4樓： defjudgePrime(n ):if n<=1: return Falsei= 2whilei* i<=n: ifn%i ==0:return Falsei+= 1return True 浪跡天涯學python 手機做答只談思路 利用資料型別轉換講數字問題變成字串比對。將數字平方讓後轉換成字串然後利用索引做切片看與數字本身轉換成字串的量是否相等。這個方法充分利用了python的內建豐富的內建函式 xufive 先統一下認識 如果乙個整數的平方的右側還是這個整數，則該整數被稱為同構數。... 魔某人 include include const char result 2 int main intNumType char Str bool dot false 小數點 char p Str charCh p if Ch Ch for Ch p p dot true elseif 9 Ch 0... cvgmt MemberQ Flatten Table i j, ProductOfTwoDigitNumberQ num Integer Block TwoDigitDivisors Divisors num IntersectingQ num TwoDigitDivisors TwoDigitD...怎麼用python判斷乙個數是否是同構數？
如何用c語言判斷乙個數為小數？
Mathematica 怎麼判斷乙個數能否由兩個兩位數相乘得到？