優化一個算法來計算max prime div

Question

該算法使用Eratosthenes篩計算最大素數div。 它需要超過7kk千字節來計算x超過1000000000 lol。

一些建議如何優化它？ 謝謝。

#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

你可以實現的優化（如使用一個位，而不是32），但它會在最讓你一個32優化的因素。

一個更有趣的事情是做算法優化（如不計算全部篩但只開方（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;