verify/spoj/spoj-MMFSUNDARAM.test.cpp

View this file on GitHub
Last update: 2022-07-21 16:12:33-04:00
Problem: https://www.spoj.com/problems/MMFSUNDARAM/

Depends on

Code

#define PROBLEM "https://www.spoj.com/problems/MMFSUNDARAM/"

#include "../../library/contest/template-minimal.hpp"
#include "../../library/number-theory/sieve.hpp"

const int N = 1e5 + 5;

Sieve<N> sieve;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int n;
	cin >> n;
	for (int x : sieve.pr) {
		if (x <= n) {
			cout << x << ' ';
		} else {
			break;
		}
	}
	cout << '\n';
	return 0;
}

#define PROBLEM "https://www.spoj.com/problems/MMFSUNDARAM/"


#include <algorithm>
#include <array>
#include <bitset>
#include <cassert>
#include <chrono>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <deque>
#include <iostream>
#include <iomanip>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <stack>
#include <string>
#include <unordered_map>
#include <vector>

using namespace std;

template <int SZ> struct Sieve {
	std::bitset<SZ> pri;
	std::vector<int> pr;
	
	Sieve() {
		pri.set();
		pri[0] = pri[1] = 0;
		for (int i = 4; i < SZ; i += 2) {
			pri[i] = 0;
		}
		for (int i = 3; i * i < SZ; i += 2) {
			if (pri[i]) {
				for (int j = i * i; j < SZ; j += 2 * i) {
					pri[j] = 0;
				}
			}
		}
		for (int i = 0; i < SZ; i++) {
			if (pri[i]) {
				pr.push_back(i);
			}
		}
	}
};

const int N = 1e5 + 5;

Sieve<N> sieve;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int n;
	cin >> n;
	for (int x : sieve.pr) {
		if (x <= n) {
			cout << x << ' ';
		} else {
			break;
		}
	}
	cout << '\n';
	return 0;
}