[已解决]这是怎么算出来是素数的？

mclb

m = input()
i = 2
while(i < int(m)+ 1):
  j = 2
  while(j <= (i/j)):
    if not(i%j):
      break
    j += 1
  if (j > i/j) :
    print(i,end=",")
  i += 1

最佳答案

月排行榜 / 总排行榜

赫尔曼·迈耶

2020-12-26 20:25:58

mclb 发表于 2020-12-26 21:51
可以简单讲解一下吗？

看不出来吗？循环条件(j <= (i/j))变换一下不就是(j*j <= i),也就是(j <= sqrt(i))
若过程中出现not(i%j)，也就是i%j = 0，则跳出循环，那么后面(j > (i/j))就不符合，i不是素数，也不会print。只有j一直无法被i整除完成整个循环，才能达成(j > (i/j))

跳转到最佳答案楼层

赫尔曼·迈耶

mclb 发表于 2020-12-26 21:51
可以简单讲解一下吗？

看不出来吗？循环条件(j <= (i/j))变换一下不就是(j*j <= i),也就是(j <= sqrt(i))
若过程中出现not(i%j)，也就是i%j = 0，则跳出循环，那么后面(j > (i/j))就不符合，i不是素数，也不会print。只有j一直无法被i整除完成整个循环，才能达成(j > (i/j))

mclb

就是疑惑,素数不是没有规律吗？
除了排除穷举除以2～自身余数为0的数,
这个是什么情况？

赫尔曼·迈耶

这个只是做了点数学上的变换，实际上相当于遍历从2到sqrt(i) 的穷举。其实这么写很不好，不易理解，性能上也没有多少提升，不用管它就好。

风过无痕1989

mclb 发表于 2020-12-26 20:27
就是疑惑,素数不是没有规律吗？
除了排除穷举除以2～自身余数为0的数,
这个是什么情况？

今天没有帖子回，就回复你一下吧（悬赏帖子由于没有系统奖励，一般情况下，没有人回答你的问题的）：
素数的规律就是除了自然数 1 和它本身外，不能被其他的自然数相除。上面的程序就是做这个反复除法的，对于每一个自然数 i ，用另一个自然数 j 去除

mclb

赫尔曼·迈耶 发表于 2020-12-26 21:45
这个只是做了点数学上的变换，实际上相当于遍历从2到sqrt(i) 的穷举。其实这么写很不好，不易理解，性能上 ...

可以简单讲解一下吗？

jackz007

n = int(input(请输入一个整数 : '))  # 键盘输入一个整数 n
f = False                            # 假定 n 不是一个素数（防止 n < 2）
if n > 1:                            # 如果 n 大于 2，再进行判断
    d , f = 3 , True                 # 假定 n 是素数，准备循环枚举因子进行检测，因子初值为 3
    while d * d < n + 1:             # 循环，结束条件是 d × d > n
        if n % d == 0 :              # 如果 d 是因子
            f = False                # 那就否定是之前的素数假设
            break                    # 直接退出循环
        d += 2                       # 如果 d 不是因子，d = d + 1 准备下一个因子的枚举和检测
if f :                               # 根据 f 标志判定检测结果
    print(n , '是素数')
else :
    print(n , '不是素数') 

mclb

赫尔曼·迈耶 发表于 2020-12-26 21:59
看不出来吗？循环条件(j

那个,我把循环条件while(j <= (i/j)):换成while True也是一样的。

mclb

赫尔曼·迈耶 发表于 2020-12-26 21:59
看不出来吗？循环条件(j

明白了,明白了,玩意写误导性太强了,not(i%j)素数已经出来了