fork download 
  1.     #include <iostream>
  2.     #include <vector>
  3.     #include <math.h>
  4.     #include <chrono>
  5.  
  6.     int main() {
  7.     	const int MAX = 200000000;
  8.     	std::vector<int> factors;
  9.  
  10.     	std::cout << "Initiallizating" << std::endl;
  11.     	auto start_time = std::chrono::steady_clock::now();
  12.     	factors.resize(MAX);
  13.     	std::cout << "Initiallization took "
  14.     		<< std::chrono::duration_cast<std::chrono::milliseconds>(std::chrono::steady_clock::now() - start_time).count()
  15.     		<< " ms" << std::endl;
  16.  
  17.     	std::cout << "Starting calculation" << std::endl;
  18.     	start_time = std::chrono::steady_clock::now();
  19.     	int upper_bound = sqrt(MAX) + 1;
  20.     	for (int i = 2; i < upper_bound; ++i) {
  21.     		if (factors[i] == 0) {
  22.     			for (int j = i; j < MAX; j += i) {
  23.     				factors[j] = i;
  24.     			}
  25.     		}
  26.     	}
  27.     	std::cout << "Calculation took "
  28.     		<< std::chrono::duration_cast<std::chrono::milliseconds>(std::chrono::steady_clock::now() - start_time).count()
  29.     		<< " ms" << std::endl;
  30.  
  31.     	std::cout << "Validating results" << std::endl;
  32.     	for (int i = 2; i < 20; ++i) {
  33.     		std::cout << i << ": ";
  34.     		if (factors[i] == i) {
  35.     			std::cout << "Is prime";
  36.     		}
  37.     		else {
  38.     			for (int N = i; N > 1; N /= factors[N])
  39.     				std::cout << factors[N] << ", ";
  40.     		}
  41.     		std::cout << std::endl;
  42.     	}
  43.  
  44.     	return 0;
  45.     }
Success #stdin #stdout 3.4s 784288KB
comments (?)
stdin 
Standard input is empty
stdout 
Initiallizating
Initiallization took 202 ms
Starting calculation
Calculation took 3187 ms
Validating results
2: Is prime
3: Is prime
4: 2, 2, 
5: Is prime
6: 3, 2, 
7: Is prime
8: 2, 2, 2, 
9: 3, 3, 
10: 5, 2, 
11: Is prime
12: 3, 2, 2, 
13: Is prime
14: 7, 2, 
15: 5, 3, 
16: 2, 2, 2, 2, 
17: Is prime
18: 3, 3, 2, 
19: Is prime
https://ideone.com/grBGBl
language:
C++14 (gcc 8.3)
created:
5 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!