MR
by Kubic @ 2019-12-10 22:39:47
线性筛?
by Ryo_Yamada @ 2019-12-10 22:39:55
@[froldH](/user/88735) 裸判断就行
by 西卡洛斯 @ 2019-12-10 22:42:08
@[北落师门123456](/user/240165) Miller-Rabin?
by Curators @ 2019-12-10 22:44:37
```cpp
bool isprime(int n) {
int t = sqrt(double(n)) + 1;
if(!(n % 2)) return false;
for(int i = 3; i <= t; i += 2) {
if(!(n % i))
return false;
}
return true;
}
```
大概……这样? 没编译过 && 慎用
by 寒鸽儿 @ 2019-12-10 22:47:25
@[froldH](/user/88735) 这样每次$O(sqrt(n) / 2)$有点复杂?
by Ryo_Yamada @ 2019-12-10 22:49:53
@[breeze末影](/user/242543) 大概$O(\sqrt{N})$这么打最方便?
诶等下忘记判断1和2了
by 寒鸽儿 @ 2019-12-10 22:50:52
加一句
```cpp
if(n == 2) return true;
```
by 寒鸽儿 @ 2019-12-10 22:51:17
@[froldH](/user/88735) 通过辽 万分感谢
by 西卡洛斯 @ 2019-12-10 22:51:18
@[北落师门123456](/user/240165) 不用谢ovo
by 寒鸽儿 @ 2019-12-10 22:52:38