[BaekJun,C++]1929: finding primes

 

https://www.acmicpc.net/problem/1929

Problem:

Write a program that prints all prime numbers between M and N, inclusive.

Input:

The natural numbers M and N are given on the first line, separated by a space. (1 ≤ M ≤ N ≤ 1,000,000) The input guarantees that there is at least one prime number between M and N.

Output:

Print the prime numbers in ascending order, one per line.

#include<iostream>
#include<cstdio>
#include<algorithm>

using namespace std;

int m, n;

int main(void) {
   cin >> m >> n;
   int size = n - m + 1;
   int* prime = new int[n + 1];
   prime[1] = 0;
   for (int i = 2; i < n + 1; i++) {
       prime[i] = 1;
   }

   //eratostheneses sieve
   for (int i = 2; i < n + 1;i++) {
       if (prime[i] == 0) {
           continue;// continue, break
       }
       else {
           for (int j = i * 2; j < n + 1; j += i) { //you don't always have to incerase the index by 1
               prime[j] = 0;
           }
       }
   }


   for (int i = m; i < n + 1; i++) {
       if (prime[i] != 0) {
           cout << i << '\n'; //\n is faster than endl;
       }
   }

   //cin >> n;
   return 0;
}

Issue:

I thought I had successfully implemented the Sieve of Eratosthenes, but I encountered a runtime error. The crucial technique here is that I was incrementing the for loop by 1.

So, initially I set the index of j (the multiples found from bottom to top) as i * 2 (since any multiple of a prime number that is 2 times the prime is not a prime). If we let j = 2i, we can save runtime, and the index increment can also be adjusted. Setting j += i allows it to increase as i * 3, i * 4, and so on.

Time Complexity: O(nlogn) - Eratosthenes' Seive