최대 소수 div를 계산하는 알고리즘을 최적화

Question

이 알고리즘은 Eratosthenes의 체를 사용하여 최대 소수 div를 계산합니다. x를 1000000000 롤 이상으로 계산하려면 7kk 킬로바이트가 필요합니다.

몇 가지 조언 내가 어떻게 최적화 할 수 있습니까? 덕분에 .

#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 비트 대신 1 비트 사용) 최대 32 개의 최적화 요소가 제공됩니다.

더 흥미로운 것은 알고리즘의 최적화 "7kk 킬로바이트"

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;