杭州建站软件,请人做网站要注意什么,响应式网站建设服务商,确定网站主题目录
判断一个数n是否是素数
求一个数的素因数个数
求大于等于指定数的最小素数 在数论中有三个非常重要的关于素数的定理
1、任何数都可以表示成若干个素数的乘积
2、任意数的素因子一个大于根号n的自然数#xff0c;另一个与其对应的因子则必小于根号n。
3、除了2和3以…目录
判断一个数n是否是素数
求一个数的素因数个数
求大于等于指定数的最小素数 在数论中有三个非常重要的关于素数的定理
1、任何数都可以表示成若干个素数的乘积
2、任意数的素因子一个大于根号n的自然数另一个与其对应的因子则必小于根号n。
3、除了2和3以外的所有素数都是6k±1型k1、2、3、...这里要反过来是不成立的也就是说6k±1型的不一定都是素数例如35是6k-1型但它不是素数
判断一个数n是否是素数
方法1遍历从2到n-1的所有因子时间复杂度
def is_prime(n):if n 2: # 小于2的肯定不是素数return 0for i in range(2, n):if n % i 0: #如果存在2到n的因子则不是素数return 0return 1 #如果2到n遍历完后都没有则是素数
方法2使用性质2我们其实可以只遍历从2到根号n此时时间复杂度降为
def is_prime(n):if n 2: # 小于2的肯定不是素数return 0for i in range(2, int(n**0.5)1): #这里int会向下取整所以加1消除误差if n % i 0: return 0return 1
方法3使用性质2和性质3从2到根号n然后每隔6个数遍历此时时间复杂度降为
def is_prime(n):if n 2: return 0if n 3: # 2或3肯定是素数return 1if n % 2 0 or n % 3 0: # 如果能整除2或3则不是素数return 0for i in range(5, int(n ** 0.5) 1, 6):#从5开始步长为6if n % i 0 or n % (i 2) 0: # i表示6k-1i2表示6k1return 0return 1求一个数的素因数个数
根据定理1任意数都可以表示为若干个素数的乘积写一个程序要求计算一个数的素因子个数
题目链接
https://www.lanqiao.cn/problems/2155/learning/?page1first_category_id1sortstudents_countcategory_id3name%E8%B4%A8%E5%9B%A0%E6%95%B0
ans 0
n int(input())
# 2和3单独讨论
for i in [2, 3]:if n % i 0: # 如果可以整除i即含有素因子ians ans 1 # 计数加1while n % i 0: # 将n一直除以i直到n中没有因子in n // ifor i in range(5, int(n ** 0.5) 1, 6): for j in [i, i 2]: # j分别表示6k-1和6k1# 以下过程与上面同理if n % j 0:ans ans 1while n % j 0:n n // jif n ! 1: # 如果最后除出来结果不是1说明还剩个素因数还需要再加1ans ans 1print(ans)输入396结果为3因为396有2、3、11三个素因子 求大于等于指定数的最小素数
def is_prime(n):if n 2:return 0if n 3:return 1if n % 2 0 or n % 3 0:return 0for i in range(5, int(n ** 0.5) 1, 6):if n % i 0 or n % (i 2) 0:return 0return 1n int(input())if is_prime(n): # 如果是素数则直接输出print(n)
else:for j in range(1, 7): # 根据性质最多隔6位肯定会有素数所以一直给n加1直到n是素数则输出n n 1if is_prime(n):print(n)break
输入17 输入35
