hello ladies and gentlemen
i want some help on making my program faster
for input N=1000000 it's runtime is 1,8 secs
i want to make it <=1 secs
here is the code, im using an implementation i made of eratosthenes algorithm to solve a problem
Code:
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
int main(void) {
int N;
FILE *fp=fopen("test.in","r");
FILE *fout=fopen("test.out","w");
fscanf(fp,"%d",&N);
fclose(fp);
int *array,i,size,k,check,*array2;
check = 0;
array = (int*)malloc(N*sizeof(int));
for (i=0;i<N;i++){
array[i] = i+1;
if ( array[i] % 2 == 0 && array[i] != 2){
array[i] = 0;
}
// printf("%d\n",array[i]);
}
array[0]=0;
for (k=3;k<sqrt(N);k++){
if (array[k-1]!=0){
for (i=k;i<N;i++){
if (i%k == 0 && i!=k){
array[i-1] = 0;
}
}
}
}
size = -1;
for (i=0;i<N;i++){
if (array[i]!=0){
size = size + 1;
}
}
array2 = (int*)malloc((size)*sizeof(int));
size = -1;
for (i=0;i<N;i++){
if (array[i]!=0){
size = size + 1;
array2[size] = array[i];
}
}
for (i=0;i<=size;i++){
for (k=0;k<=size;k++){
if (N == (array2[i] + array2[k])){
fprintf(fout,"%d %d\n",array2[i],array2[k]);
fclose(fout);
check = 1;
break;
}
}
if (check == 1){
break;
}
}
free(array);
free(array2);
return 0;
}
thank you