C语言中的素数因子
C语言中的素数因子
提问于 2018-06-09 06:01:36
我偶然发现了这个有效的程序，它可以打印给定数字的所有素因数：
# include <stdio.h>
# include <math.h>
// A function to print all prime factors of a given number n
void primeFactors(int n)
{
// Print the number of 2s that divide n
while (n%2 == 0)
{
printf("%d ", 2);
n = n/2;
}
// n must be odd at this point. So we can skip
// one element (Note i = i +2)
for (int i = 3; i <= sqrt(n); i = i+2)
{
// While i divides n, print i and divide n
while (n%i == 0)
{
printf("%d ", i);
n = n/i;
}
}
// This condition is to handle the case when n
// is a prime number greater than 2
if (n > 2&&n%2!=0)
printf ("%d ", n);
}
/* Driver program to test above function */
int main()
{
int n = 315;
primeFactors(n);
return 0;
}输出是3 3 5 7。太完美了。
但是我在这个算法中有一个困惑。sqrt()返回一个浮点值。如果它以整数格式显示在printf中，它将返回某个随机的大数字。如果是这种情况，则for循环中的条件应该失败，因为sqrt()作为整数返回一个随机数。有没有人能解释一下？
另外，有人能证实这一点吗？这个算法在geeksforgeek网站中被错误地写成if(n>2)而不是if(n>2&&n!=0)，这是我添加的。请谁来验证一下这个算法。提前谢谢。
回答 1
Stack Overflow用户
发布于 2018-06-09 18:36:10
其他人建议预先计算整数平方根，但您需要小心根据需要重新计算它。对于主循环，我将使用如下内容：
// n must be odd at this point. So we can skip
// one element (Note i = i +2)
int limit = isqrt(n); // Calculate integer square root.
for (int i = 3; i <= limit; i = i+2)
{
// While i divides n, print i and divide n
if (n % i == 0)
{
printf("%d ", i);
n = n / i;
while (n%i == 0)
{
printf("%d ", i);
n = n / i;
}
// Recalculate limit as n has changed.
limit = isqrt(n);
}
}这只会在被测试的数字发生变化时重新计算平方根。我使用isqrt(n)来指示执行实际计算的函数。在我自己的代码中，我使用了牛顿-拉夫森方法，但也有其他可能的方法。
你最后的测试可以简化为：
// This condition is to handle the case when n
// is a prime number greater than 2
if (n > 1)
{
printf ("%d ", n);
}至多有一个质数因子大于数的平方根。这个单独的因子(如果存在)将是所有较小的素数因子被分开后的余数。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/50768926
复制相关文章
相似问题