Prime 与否 Prime 输出慢

Question

这是C程序。下面是我的code。我在终端中使用了 nano 。当我用 ./a.out 9872349901 编译和测试时，我花了整整一分钟才得到结果......有人知道为什么它很慢吗？（我相信它可能是太长的数字，但我使用 int isprime(long long n) {This is for my CS course class 当我做 labcheck 时，它是自动分配分数来获得分数，但它不会显示我的，因为labcheck 不会等待它。

/**
 * 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 > 1\n") 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 != '[=10=]')
    {
        printf ("input wrong\n");
        return -1;
    }
    int result = isprime(n);

    if (result == 1)
        printf ("%lld is prime\n", n);
    else
        printf ("%lld is not prime\n", n);
    return 0;
}

许多不同的数字都能完美地工作，但 9872349901 却不行，因为这是教师要测试我的作业的数字。

这是我做时的预览 "lab check"

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 for 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)；你使用 i * i <= N。或者，如果必须使用 sqrt(N)，则在循环之前计算值并使用计算值，四舍五入到下一个整数（ceil() 来自 <math.h>）。至少，这是我几年前的基准测试告诉我的。

JFTR：将上面的代码转移到问题中的代码中，计时 p4 9872349901 产生报告，它在大约 0.005 秒的经过时间（在普通的 2016 15" MacBook Pro 上） 2.7 GHz Intel Core i7 处理器）。我还尝试了 98723499017333（在数字的右端添加 4 位数字，并在点击这个数字之前得到一些非素数），它在 0.044 秒内被报告为素数。当然，非主要报告更快。

Prime 与否 Prime 输出慢

Prime or not Prime output slow

c

primes

integer

slowdown