fork(1) download
copy 
  1. #include <vector>
  2. #include <iterator>
  3. #include <algorithm>
  4. #include <iostream>
  5. #include <cassert>
  6.  
  7. auto sieve(int limit) {
  8. 	std::vector<bool> primes_lookup(limit);
  9. 	// kod z neta
  10. 	unsigned long long int i,j;
  11.  
  12.     for (i=2;i<limit;i++)
  13.     	primes_lookup[i]=1;
  14.  
  15.     for (i=2;i<limit;i++)
  16.     	if (primes_lookup[i])
  17.             for (j=i;i*j<limit;j++)
  18.                 primes_lookup[i*j]=0;
  19.  
  20. 	return primes_lookup;
  21. }
  22.  
  23. template<typename Cont>
  24. auto extract_primes(Cont const &primes_lookup) {
  25. 	std::vector<int> result;
  26. 	for (int i = 0; i < primes_lookup.size(); ++i) {
  27. 		if (primes_lookup[i]) {
  28. 			result.push_back(i);
  29. 		}
  30. 	}
  31. 	return result;
  32. }
  33.  
  34. template<typename Cont>
  35. auto calc_factors(Cont const &primes, int num) {
  36. 	std::vector<int> result;
  37.  
  38. 	for (int i = 0; i < primes.size() && primes[i] <= num;) {
  39. 		if (num % primes[i]) {
  40. 			i += 1;
  41. 			continue;
  42. 		} else {
  43. 			result.push_back(primes[i]);
  44. 			num /= primes[i];
  45. 		}
  46. 	}
  47. 	return result;
  48. }
  49.  
  50. int main() {
  51. 	auto const primes = extract_primes(
  52. 		sieve(100000)
  53. 	);
  54.  
  55. 	auto calc_factors = [&primes](int num) {
  56. 		return ::calc_factors(primes, num);
  57. 	};
  58.  
  59. 	// a spróbuj tylko pchać jakieś factorsy które nie są posortowane i które nie są l. pierwszymi
  60. 	auto condition = [&primes](auto factors) -> bool {
  61. 		if (!factors.size()) return false;
  62.  
  63. 		auto last = std::unique(std::begin(factors), std::end(factors));
  64. 		return std::equal(
  65. 			std::begin(factors),
  66. 			last,
  67. 			std::find(std::begin(primes), std::end(primes), factors[0])
  68. 		);
  69. 	};
  70.  
  71. 	for(int num = 0; std::cin >> num;) {
  72. 		auto factors = calc_factors(num);
  73. 		std::cout
  74. 			<< (condition(factors)? "warunek spelnia " : "warunku nie spelnia ")
  75. 			<< num
  76. 			<< " -> ";
  77.  
  78. 		for(auto el: factors) std::cout << el << " ";
  79.  
  80. 		std::cout << std::endl;
  81. 	}
  82. 	return 0;
  83. }
  84.  
Success #stdin #stdout 0s 4212KB
comments (?)
stdin
copy 
12 55 130 1 2 10 300 13
stdout
copy 
warunek spelnia 12 -> 2 2 3 
warunku nie spelnia 55 -> 5 11 
warunku nie spelnia 130 -> 2 5 13 
warunku nie spelnia 1 -> 
warunek spelnia 2 -> 2 
warunku nie spelnia 10 -> 2 5 
warunek spelnia 300 -> 2 2 3 5 5 
warunek spelnia 13 -> 13
https://ideone.com/St5yH2
language:
C++14 (gcc 8.3)
created:
6 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!