fork download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. #include <cstdint>
  4. #include <limits>
  5.  
  6. //#include "PrimeDivTest.h"
  7.  
  8. #pragma once
  9. //#include <vector>
  10. #include <algorithm>
  11.  
  12.  
  13. template<class T>
  14. class PrimeDivTest {
  15. public:
  16. 	PrimeDivTest() {
  17. 		Clear();
  18. 	}
  19.  
  20. 	bool Clear() {
  21. 		Primes.clear();
  22. 		Count = 2;
  23. 		//Primes.push_back(2);
  24. 		return true;
  25. 	}
  26.  
  27. 	std::size_t Size() const {
  28. 		return Primes.size();
  29. 	}
  30.  
  31. 	bool IsPrime(const T& In) {
  32. 		Search(In);
  33.  
  34. 		auto it = std::find(Primes.begin(), Primes.end(), In);
  35.  
  36. 		return it != Primes.end() ? ((*it) == In) : false;
  37. 	}
  38.  
  39. 	bool Search(const T& In) {
  40. 		for (Count; Count <= In; Count++) {
  41. 			bool F = true;
  42. 			for (auto& o : Primes) {
  43. 				if (Count % o == 0) {
  44. 					F = false;
  45. 					break;
  46. 				}
  47. 				if (o * o >= Count) { break; }
  48. 			}
  49. 			if (F) {
  50. 				Primes.push_back(Count);
  51. 			}
  52. 		}
  53.  
  54. 		std::sort(Primes.begin(), Primes.end());
  55.  
  56. 		return true;
  57. 	}
  58.  
  59. 	const T& operator[](std::size_t Idx) const {
  60. 		return Primes[Idx];
  61. 	}
  62.  
  63. 	typename std::vector<T>::const_iterator begin() {
  64. 		return Primes.cbegin();
  65. 	}
  66. 	typename std::vector<T>::const_iterator end() {
  67. 		return Primes.cend();
  68. 	}
  69. protected:
  70. 	std::vector<T> Primes;
  71. 	T Count = 2;
  72. };
  73.  
  74. template<class T>
  75. bool MillerRabinPrimalityTest(const T& In) {
  76. 	if (In / 21 == 0) { return false; }
  77. 	if (In / 16 == 0) { return false; }
  78. 	if (In / 32 == 0) { return false; }
  79.  
  80. 	return true;
  81. }
  82.  
  83. template<class T>
  84. std::vector<T> PrimeFactorization(T In) {
  85. 	std::vector<T> R;
  86.  
  87. 	for (T i(2); i <= In; i++) {
  88. 		if(In%i==0){
  89. 			R.push_back(i);
  90. 			In /= i;
  91.  
  92. 			if (MillerRabinPrimalityTest(i)&&(i<=In)) {
  93. 				R.push_back(i);
  94. 				In /= i;
  95.  
  96. 			}
  97. 			std::cout << i << ":" << In << std::endl;
  98. 			i--;
  99.  
  100. 		}
  101. 	}
  102.  
  103. 	return R;
  104. }
  105.  
  106. typedef std::uintmax_t Ty;
  107.  
  108. int main() {
  109.  
  110. 	auto R = PrimeFactorization<Ty>(std::numeric_limits<Ty>::max());
  111.  
  112. 	PrimeDivTest<Ty> PDT;
  113.  
  114. 	for (auto& o : R) {
  115. 		std::cout << o << ',';
  116. 		if (PDT.IsPrime(o)) {
  117. 			std::cout << "PDT Safe";
  118. 		}
  119. 		std::cout << std::endl;
  120. 	}
  121.  
  122. 	return 0;
  123. }
  124.  
Success #stdin #stdout 0.03s 4300KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
3:6148914691236517205
5:1229782938247303441
17:72340172838076673
257:1095250084605
285:13484150
269683:50
3,PDT Safe
5,PDT Safe
17,PDT Safe
257,PDT Safe
257,PDT Safe
285,
285,
269683,PDT Safe
https://ideone.com/vJRbP1
language:
C++14 (gcc 8.3)
created:
3 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!