在计算b=5000000显示时间超限，想知道哪里可以优化一下？以及怎么优化才好

Question

#include<stdio.h>
#include<math.h>
int sushu(int num)
{
int c=0;
for (int s = 3; pow(s,2) <= num; s=s+2)
{
if ((num % s) == 0)
c++;
}
return c;
}
int main()
{
int k,a,b;
scanf("%d", &k);
for (; k > 0; k--)
{
int n = 0,i,p,q;
scanf("%d %d", &a, &b);
{
if ((a % 2) == 0)
{
a = a + 1;
}
for (i = a; (i + 2) <= b; i = i + 2)
{
p=sushu(i);
q=sushu(i+2);
if ((p+q) == 0)
n++;
}
if (a == 1)
{
if (n != 0)
n = n - 1;
}
printf("%d\n", n);
}
}
}

在计算b=5000000显示时间超限，想知道哪里可以优化一下？以及怎么优化才好

Answer 1

貌似你在统计孪生素数的数量。

判断素数哪里，如果发现num有因子直接返回1就好，不用在继续模下去了，应为它肯定不是个素数。

int sushu(int num) {
    for (int s = 3; pow(s, 2) <= num; s = s + 2) {
        if ((num % s) == 0)
            return 1;
    }
    return 0;
}

上面优化后，面对5000000这样大的数字，我估计还是可能超时。你先试一下，如果还超时，我们就要用筛法了。筛法实现见下方：

#include <stdio.h>
#include <string.h>


int main() {
    int k;
    scanf("%d", &k);
    for (; k > 0; k--) {
        int a, b;
        scanf("%d %d", &a, &b);
        int arr[b + 1];
        memset(arr, 1, sizeof(arr));
        for (int i = 2; i * i <= b; i += 1) {
            if (arr[i]) {
                int k = i * 2;
                while (k <= b) {
                    arr[k] = 0;
                    k += i;
                }
            }
        }
        int prev = 0, count = 0;
        for (int i = a; i <= b; i++) {
            if (arr[i]) {
                if (i - prev == 2) {
                    count++;
                }
                prev = i;
            }
        }

        printf("%d\n", count);
    }
    return 0;
}

当然上面的代码也有其问题，就是要在栈上开辟一个5M左右的大数组。很多编译器给程序分配的栈空间只有1M。此时可以在编译时指定栈大小gcc --stack 5242880 main.c，或者改为在堆上开辟数组。下面是改用堆上开辟数组空间。

#include <stdio.h>
#include <stdlib.h>
#include <string.h>


int main() {
    int k;
    scanf("%d", &k);
    for (; k > 0; k--) {
        int a, b;
        scanf("%d %d", &a, &b);
        int *arr = (int *)malloc((b + 1) * sizeof(int));
        memset(arr, 1, sizeof(arr));
        for (int i = 2; i * i <= b; i += 1) {
            if (arr[i] == 0) {
                int k = i * 2;
                while (k <= b) {
                    arr[k] = 1;
                    k += i;
                }
            }
        }
        int prev = 0, count = 0;
        for (int i = a; i <= b; i++) {
            if (arr[i] == 0) {
                if (i - prev == 2) {
                    count++;
                }
                prev = i;
            }
        }

        printf("%d\n", count);
        free(arr);
    }
    return 0;
}