Sieve of Eratosthenes - YessineJallouli/Competitive-Programming GitHub Wiki

#include <bits/stdc++.h>
#define ll long long
#define SaveTime ios_base::sync_with_stdio(false), cin.tie(0);
using namespace std;

const int N = 1e6;
int sieve[N];

vector<int> factorize(int n) {
   vector<int> ans;
   while (n != 1) {
      ans.push_back(sieve[n]);
      n/= sieve[n];
   }
   return ans;
}

int main() {
   SaveTime
   memset(sieve, -1, sizeof sieve);
   for (int i = 2; i < N; i++) {
      if (sieve[i] == -1) {
         for (int j = i; j < N; j+= i)
            if (sieve[j] == -1)
               sieve[j] = i;
      }
   }
}