c - 优化计算最大素数除法的算法

Question

该算法使用埃拉托斯特尼筛法计算最大素数 div。 计算 x 超过 1000000000 需要超过 7kk KB 哈哈。

一些建议我如何优化它？ 谢谢。

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

int main()
{
int x, p, i, q, max, min;
scanf ("%d", &x);
int *a = (int*)malloc((abs(x)+1) * sizeof(int));
for (i=0; i<=abs(x); i++)
    a[i] = i;
a[1]=0;
for (p=2; p<=abs(x); p++){
        for (q=p*2; q<=abs(x); q+=p)
            a[q]=0;
} 
max=0;
if (x>=0){
    for(i=0; i<=abs(x); i++)
        if((a[i]!=0) && (abs(x)%a[i]==0))
            if (a[i]>max)
                max=a[i];
printf("%d", max);
free(a);
}
else{
min=abs(x);
for(i=0; i<=abs(x); i++)
        if((a[i]!=0) && (abs(x)%a[i]==0))
            if (a[i]<min)
                min=a[i];
printf ("%d", -min);
free(a);
}
}

Answer 1

您可以进行实现优化(例如使用 1 位而不是 32 位)，但最多只能获得 32 的优化因子。

更有趣的事情是进行算法优化(例如不计算整个筛子，而只计算 sqrt(x))

int x, p, i, q;
scanf_s("%d", &x);
x = abs(x);
int size = sqrt(x); // there is at most one prime number that divide x bigger than sqrt(x)
int *a = (int*)malloc((size + 1) * sizeof(int));
for (i = 0; i <= size; i++)
    a[i] = i;
a[1] = 0;
for (p = 2; p <= size; p++) {
    if (a[p] == 0) { // p is not prime you can skip p
    }
    else {
        while (x % p == 0) { // if p div x, divide it as much as possible
            x /= p;
        }
        if (x == 1) {
            printf("%d", p); 
            break;
        }
        for (q = p * p; q <= size; q += p)
            a[q] = 0;
    }
}
if (x != 1)
    printf("%d", x);
    free(a);
return 0;