C25夏令营结营赛
埃氏筛是这么写的吗？
C24zhouyanchen LV 7 @ 2025-7-30 11:01:32

代码第16行第2层循环里int j=i*i确定没问题吗，是否应当改为int j=i*2?

还是我记错了

抑或是都可以？

好吧后来我发现这是可以的，请先想一想是为什么，然后看nPr在下面的评论吧=）

~~肯定不是我懒得写了，还有不要@C25fengwentao~~

C24zhengfujia LV 9 @ 2025-8-5 16:02:36

没有问题的。

因为 i * 2 在 $i$ 为 $2$ 的时候就被筛掉了。

小于 $i$ 的所有质数都已经筛过了。

所以如果 $i$ 是质数，从 i * i 开始就行了。

=）

👍 3

❤️ 3

😄 3

👀 2
- C24zhouyanchen LV 7 @ 2025-8-8 20:24:44
  
  即i*2到i*(i-1)的数一定有一个小于i的因数，肯定在之前的循环里被筛掉了