1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
/* AUTHOR: Loukas Xanthos
 * PROGRAM: Sieve of Eratosthenes
 * Improved answer for a programming competition.
 */
 
#include <stdio.h>
#include <stdlib.h>
 
#define llint unsigned long long int
 
llint N, primes, i, j, arrayid;
bool * koskino; /* numbers marked as Non-primes*/
 
inline void showresults(bool showallprimes, bool showquantity)
{
  if(showallprimes == false){
    primes++; /*Don't forget the prime 2*/
    for(i=3; i<=N; i += 2)
    {
      if(koskino[i] == false) primes++;
    }
    printf("%lld\n", primes);
  }
  
  if(showallprimes == true && showquantity == false){
    printf("%d ", 2); /*Don't forget the prime 2*/
    for(i=3; i<=N; i += 2)
    {
      if(koskino[i] == false) printf("%lld ", i);
    }
  }
  if(showallprimes == true && showquantity == true){
    printf("%d ", 2); primes++; /*Don't forget the prime 2*/
    for(i=3; i<=N; i += 2){
      if(koskino[i] == false){ printf("%lld ", i); primes++;}
    }
    printf("\n%lld\n", primes);
  }
  
}
 
int main()
{
  scanf("%lld", &N);
  
  koskino = (bool*) malloc( (N + 1) * sizeof(int));
  
  for (i=2; i<=N; ++i)
  {
     if(koskino[i] == false)
     {
       for(j=2; j<=N; ++j)
       {
         if(i*j <= N) koskino[j*i] = true;
         else break;
       }
     }
  }
  
  showresults(true, true);
  
  free(koskino);
 
  return 0;
}