어디까지 줄여낼 수 있을까요 ㅜ.ㅜ


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

#define MAX 100000

typedef struct data{
unsigned long int data;
int flag;
}data;

void calc_prime(data *prime);
void calc_prime2(data *prime);

void calc_prime(data *prime){
unsigned long int i, j;
for(i=2;i<MAX;i++){
prime[i].data = i;
prime[i].flag = 0;
}

printf("hello!\n");

for(i=2;i<MAX;i++){
for(j=2;j<i;j++){
if(prime[i].data % j == 0){
prime[i].flag = 1;
break;
}
}
}
return;
}

void calc_prime2(data *prime){
unsigned long int i, j;
int *temp;
int temp_len;
temp = (int *)calloc(MAX,sizeof(int));

for(i=2;i<MAX;i++){
prime[i].data = i;
prime[i].flag = 0;
}

for(i=4;i<MAX;i+=2)
prime[i].flag = 1;
for(i=6;i<MAX;i+=3)
prime[i].flag = 1;
for(i=10;i<MAX;i+=5)
prime[i].flag = 1;
for(i=14;i<MAX;i+=7)
prime[i].flag = 1;
for(i=22;i<MAX;i+=11)
prime[i].flag = 1;

temp[0] = 2;
temp[1] = 3;
temp[2] = 5;
temp[3] = 7;
temp[4] = 11;

temp_len = 5;

for(i=temp[temp_len-1]+1;i<MAX;i++){
if(i%(MAX/10) == 0)
printf("%d/%d 진행중.\n",i,MAX);
if(prime[i].flag == 1)
continue;
for(j=4;j<temp_len;j++){
if(prime[i].data % temp[j] == 0){
prime[i].flag = 1;
break;
}
}

if(prime[i].flag == 0){
temp[temp_len] = prime[i].data;
temp_len++;
}
}
prime[0].flag = 1;
prime[1].flag = 1;

return;
}


첫번째껀 O(n^2) 으로 돌아가는 막장 소스이고
두번째껀 O(n^2 / log n)으로 돌아가는 아주쪼끔 나아진 소스이고,,,

어떻게 하면 더 줄여볼 수 있을까요 

정말 시간복잡도 문제가 중요하네요..
만약 O(n)으로 만들어낼 수 있으면 순식간에 돌아가는데
O(n^2)만 가도,,, 안드로로 가버리네요 속도가 ㅋㅋ;;
방학이라서,, 여유로우니 이런 고민도 해보는군요 ㅋㅋ