c++ function to check if a number is a prime(用于检查数字是否为素数的C++函数)
本文介绍了用于检查数字是否为素数的C++函数的处理方法,对大家解决问题具有一定的参考价值,需要的朋友们下面随着小编来一起学习吧!
问题描述
bool prime (long long int n) {
bool prime = 1;
if (n == 1) {
return 0;
}
else {
for (long long int i = 2; i <= n/2 ; i++) {
if (n % i == 0) {
prime = 0;
break ;
}
}
return prime;
}
}
这是我的函数,用于检查n
是否为素数。它一直有效,直到我尝试一个12位数字,如n=999999999989。
这是针对problem on codeforces的;当我提交此函数时,网站会打印超出时间限制。
推荐答案
您的代码的时间复杂度为O(n/2)->;O(N)。 如果n是10^12(给定1秒只能做10^8左右的运算),则检查n的素性大约需要10000秒。
for (long long int i = 2; i <= n/2 ; i++) {
if (n % i == 0) {
prime = 0;
break ;
}
这里的诀窍是,您不需要检查i从2到n/2。相反,您可以将其从2减少到Sqrt(N)。这样做是因为,因为SQRT(N)*SQRT(N)是n,所以不应该有任何x和y,所以x>;SQRT(N);y>;SQRT(N);x*y=n。因此,如果n的除数存在,它应该是<;=SQrt(N)。
因此您应该将循环更改为此
for (long long int i = 2; i*i <= n ; i++) {
if (n % i == 0) {
prime = 0;
break ;
}
}
该码的时间复杂度为O(Sqrt(N)),这应该足以满足n
=10^12。
P.S:Sqrt(N)表示n的平方根
这篇关于用于检查数字是否为素数的C++函数的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持编程学习网!
沃梦达教程
本文标题为:用于检查数字是否为素数的C++函数
基础教程推荐
猜你喜欢
- 设计字符串本地化的最佳方法 2022-01-01
- C++,'if' 表达式中的变量声明 2021-01-01
- 运算符重载的基本规则和习语是什么? 2022-10-31
- C++ 程序在执行 std::string 分配时总是崩溃 2022-01-01
- 您如何将 CreateThread 用于属于类成员的函数? 2021-01-01
- 什么是T&&(双与号)在 C++11 中是什么意思? 2022-11-04
- 如何定义双括号/双迭代器运算符,类似于向量的向量? 2022-01-01
- 如何在 C++ 中处理或避免堆栈溢出 2022-01-01
- C++ 标准:取消引用 NULL 指针以获取引用? 2021-01-01
- 调用std::Package_TASK::Get_Future()时可能出现争用情况 2022-12-17