c-Prime或not Prime输出缓慢

Question

这是C程序。这是我在下面的code。我在终端中使用了nano。当我用./a.out 9872349901编译和测试时，但我花了整整一分钟的时间才得到结果。。。有人知道它为什么慢吗？(我认为这个数字可能太长了，但我使用了int isprime(long long n) {。这是我在CS课程课上做实验室检查时使用的，它是自动分配分数，但它不会显示在我的分数上，因为实验室检查不会等待它。

/**
* Make a function called isprime that returns true (i.e. 1) if the integer
* number passed to it is prime and false (i.e. 0) if it is composite (i.e.
* not prime.)  A number is composite if it is divisible by 2 or any odd number
* up to the square root of the number itself, otherwise it is prime.
* Hint: n is divisible by m if (n % m == 0)
*/
/**
* Using the isprime function you made above, test if a number provided on the
* command line is prime or not. The program should print a usage message if no
* number is provided ("Usage: p4 <number>n") and print a warning if the number
* is less than 2 ("input number should be > 1n") and should be able to handle
* numbers greater than 4 billion.
* 
* Example input/output:
* ./p4 9872349901
* 9872349901 is prime
* ./p4 65
* 65 is not prime
*/
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <limits.h>
int isprime(long long n) {
for (long long i = 2; i != n; ++i)
if (n%i == 0)
return 0;
return 1;
}
int main (int argc, char *argv[])
{
if (argc < 2)
{
printf ("Usage: p4 <number>n");
return -1;
}
char* p;
long long n = strtoll(argv[1], &p, 10);
if (n < 2 || *p != '')
{
printf ("input wrongn");
return -1;
}
int result = isprime(n);
if (result == 1)
printf ("%lld is primen", n);
else
printf ("%lld is not primen", n);
return 0;
}

许多不同的数字都很适用，但9872349901却不适用，因为这是老师测试我作业的数字。

这是我做"实验室检查"时的预览

cs25681@cs:/instructor/class/cs25681/cs/h5> labcheck 5
Checking assignment #5:
p1:
p2:
p3:
p4:
-3.0 output of program (p4) is not correct for input '9872349901':
------ Yours: ------
---- Reference: ----
9872349901 is prime
--------------------
p5:
p6:
p7:
p8:

我想为每个不同的数字测试它，所以这里是./a.out <number>的预览

cs25681@cs:/lecture/class/cs25681/cs> ./a.out 3
3 is prime
cs25681@cs:/lecture/class/cs25681/cs> ./a.out 1
input wrong
cs25681@cs:/lecture/class/cs25681/cs> ./a.out 9
9 is not prime
cs25681@cs:/lecture/class/cs25681/cs> ./a.out 9872349901
9872349901 is prime
cs25681@cs:/lecture/class/cs25681/cs> echo "took 43 seconds to output"
took 43 seconds to output
cs25681@cs:/lecture/class/cs25681/cs> 

Answer 1

^{将我的评论转换为答案}

用途：

for (long long i = 2; i * i <= n; ++i)

这限制了测试，直到i刚好大于n的平方根，正如代码中的注释所建议的那样。

一个更好的算法是测试2，然后测试奇数3、5、7…，这将大大减少测试量。

更好的是，测试2和3，然后测试6*N±1，N=1，2，3，…，测试5，7，11，13，17，19，23，25(这是它第一次没有选择素数对(，等等。

if (n <= 1)
return 0;
if (n == 2 || n == 3)
return 1;
if (n % 2 == 0 || n % 3 == 0)
return 0;
for (unsigned long long x = 5; x * x <= n; x += 6)
{
if (n % x == 0 || n % (x + 2) == 0)
return 0;
}
return 1;

请注意，您不使用sqrt(N)；您使用CCD_ 9。或者，如果必须使用sqrt(N)，则在循环之前计算值，并使用计算值，四舍五入到下一个整数(<math.h>中的ceil()(。至少，这是我几年前的基准测试告诉我的

JFTR：将上面的代码转换为问题中的代码，计时p4 9872349901会在大约0.005秒的时间内(在配备2.7 GHz英特尔酷睿i7处理器的普通2016款15英寸MacBook Pro上(得出它是素数的报告。我还尝试了98723499017333(在数字的右端加上4位数字，在点击这个数字之前得到了一些非素数(其被报告为0.044秒内的素数。当然，非主要报告的速度更快。