// n > 0 bool IsPrime(int n) { if (n 1 void PrimeList(int n) { bool* primalities = new bool[n+1]; // 0 and 1 are not prime numbers // all others can be set to true memset(primalities + 2, true, n-1); int p = 2; // Smallest prime number while (p*p <= n) // '=' is necessary, for example p = 11 { // Set multiples of p as non-prime numbers // Here you don't have to start with 'int x = p+1' // Instead, 'int x = p*p' is enough for (int x = p*p; x <= n; x += p) primalities[x] = false; // Move to the next prime number; while(!primalities[++p]); } for (int c = 0, p = 2; p <= n; ++p) if (primalities[p]) printf("%4d%c", p, (++c)%10 ? ' ' : '\n'); printf("\n"); delete[] primalities; }