001      /*    Author Malte Pagel    */
002      
003      #include <stdio.h>
004      #include <stdlib.h>
005      #include <math.h>
006      
007      
008      #define MAX_PRIMES 1000000
009      #define SHOW_ALL 0
010      
011      
012      void show_primes(int, long*);
013      int get_largest_prime_to_store();
014      
015      int total_count;
016      
017      
018      void show_primes (int upper_limit, long * primes_to_show) {
019              int i;
020              for ( i = 0; i <= upper_limit; i++ ) {
021                      printf( "%ld\t", primes_to_show[i] );
022                      if ( total_count % 5 == 4 )
023                              printf( "\n" );
024                      total_count++;
025              }
026      }
027      
028      int get_largest_prime_to_store () {
029              int largest_estimated = MAX_PRIMES * 10;
030              int tmp = 0;
031              int largest;
032              
033              while ( tmp < MAX_PRIMES ) {
034                      largest_estimated = largest_estimated * sqrt(2);
035                      tmp = largest_estimated / log(largest_estimated);
036              }
037              largest = sqrt(largest_estimated);
038              
039              return largest;
040      }
041      
042      
043      int main () {
044              int i, max, s;
045              long l, last_prime;
046              int is_prime;
047              
048              int store_it = 1;
049              int show_index = 1;
050              int count = 1;
051              
052              int largest_prime_to_store = get_largest_prime_to_store();
053              int stored_primes_size = sqrt(2) * largest_prime_to_store / log(largest_prime_to_store);
054              int package_size = sqrt(MAX_PRIMES) * sqrt(2) + 1;
055              int initial_package_size = package_size + 1;
056              
057              long * stored_primes;
058              stored_primes = malloc(stored_primes_size * sizeof(long));
059              long * shown_primes;
060              shown_primes = malloc((package_size + 1) * sizeof(long));
061              
062              stored_primes[0] = 2;
063              shown_primes[0] = 2;
064              
065              total_count = 0;
066              
067              for ( l = 3; count < MAX_PRIMES; l += 2 ) {
068                      is_prime = 1;
069                      max = count;
070                      s = sqrt(l);
071                      for ( i = 1; i < max; i++ ) {
072                              if ( stored_primes[i] > s )
073                                      break;
074                              if ( l % stored_primes[i] == 0 ) {
075                                      is_prime = 0;
076                                      break;
077                              }
078                      }
079                      if ( is_prime ) {
080                              if ( store_it && l > largest_prime_to_store )
081                                      store_it = 0;
082                              if ( store_it )
083                                      stored_primes[count] = l;
084                              
085                              shown_primes[show_index] = l;
086                              if ( !SHOW_ALL )
087                                      last_prime = l;
088                              if ( show_index < package_size )
089                                      show_index++;
090                              else {
091                                      if ( SHOW_ALL )
092                                              show_primes(show_index, shown_primes);
093                                      show_index = 0;
094                                      package_size--;
095                              }
096                              
097                              count++;
098                      }
099              }
100              
101              if ( show_index && SHOW_ALL )
102                      show_primes(--show_index, shown_primes);
103              
104              printf( "\n" );
105              if ( SHOW_ALL )
106                      printf( "%i primes found and shown", total_count );
107              else
108                      printf( "%ith prime is %ld", MAX_PRIMES, last_prime );
109              printf( "\n" );
110              printf( "Memory used to show primes: %i integers", initial_package_size );
111              printf( "\n" );
112              printf( "Memory used to store primes: %i integers", stored_primes_size );
113              printf( "\n\n" );
114              
115              free(stored_primes);
116              free(shown_primes);
117              
118              return 0;
119      }
120