Estoy haciendo un ejercicio de optimización de código y tengo que optimizar el siguiente:

#include <stdio.h> void show_primes(int *primes, int max){     int cont;     int aux;     for(cont=0; cont<max-1; cont=cont+1){         if(primes[cont] == 1){             aux = cont + 2;             printf("%d", aux);             printf(" ");                         }     } } int is_prime(int number){     int prime=1;//por defecto es primo     int divisors=2;     while(divisors<number  && prime!=0)     {         if(number%divisors==0){             prime = 0;         }         divisors++;     }     return prime; } int main() {     //Se entiende que el usuario va a introducir datos legitimos, por lo que      //no voy a comprobar si los datos de entrada pueden provocar una excepcion      //para ahorrar tiempo en el desarrollo de la practica dado que el objeto     //de la practica no consiste en hacer un software robusto, si no optimo.     int max = 518103; //introducir el numero maximo para la criba     int cont;     int primes[max];     for(cont=0; cont<max-1; cont=cont+1){         primes[cont] = is_prime(cont+2); //1 si es primo 0 si no     }     show_primes(primes,max);     return 0; } 

Actualmente, mi algoritmo (está poco optimizado a propósito) solo es capaz de calcular hasta 518103 números de la criba.

Tengo que ser capaz de optimizarlo para que calcule números superiores a 2^31.

He intentado utilizar malloc y unsigned long int, pero llega al mismo número máximo y tarda lo mismo.

#include <stdio.h> #include <stdlib.h> void show_primes(unsigned long int *primes, unsigned long int max){     unsigned long int cont;     unsigned long int aux;     for(cont=0; cont<max-1; cont=cont+1){         if(primes[cont] == 1){             aux = cont + 2;             printf("%d", aux);             printf(" ");                         }     } } int is_prime(unsigned long int number){     int prime=1;//por defecto es primo     unsigned long int divisors=2;     while(divisors<number  && prime!=0)     {         if(number%divisors==0){             prime = 0;         }         divisors++;     }     return prime; } int main() {     //Se entiende que el usuario va a introducir datos legitimos, por lo que      //no voy a comprobar si los datos de entrada pueden provocar una excepcion      //para ahorrar tiempo en el desarrollo de la practica dado que el objeto     //de la practica no consiste en hacer un software robusto, si no optimo.     unsigned long int *primes;     unsigned long int max = 518103; //introducir el numero maximo para la criba - 518103     primes = (unsigned long int *)calloc( max, sizeof( unsigned long int ) ); //      if( puntero != NULL ){ //          printf( "Allocated\n" ); //      }else{ //              printf( "Can't allocate memory\n" ); //          }     unsigned long int cont;     for(cont=0; cont<max-1; cont=cont+1){         primes[cont] = is_prime(cont+2); //1 si es primo 0 si no     }     show_primes(primes,max);     free(primes);     return 0; } 

Además, no puedo eliminar los números no primos de la lista, por lo que puedo optimizar el tiempo más, pero yo de momento quiero optimizar la memoria.

¿Alguien podría ayudarme?

PD: Se que hay soluciones ya implementadas y óptimas, pero tiene que ser hecho por mi para que no lo consideren plagio.

Muchas gracias