fork download
copy 
  1. #include <algorithm>
  2. #include <cstdlib>
  3. #include <iostream>
  4. #include <memory>
  5. #include <string>
  6. #include <vector>
  7.  
  8. using namespace std;
  9.  
  10. class UBigInt;
  11.  
  12. extern bool primalityTestMillerRabin(const UBigInt& p, const unsigned long& cnt = 100);
  13.  
  14. class UBigInt {
  15. public:
  16.     UBigInt(const bool& bit = false);
  17. 	UBigInt(const shared_ptr<vector<bool> >& bits);
  18. 	UBigInt(const unsigned long& val);
  19. 	UBigInt(const UBigInt& num);
  20. 	UBigInt operator +(const UBigInt& ade) const;
  21. 	UBigInt operator -(const UBigInt& sub) const;
  22. 	UBigInt operator *(const UBigInt& mer) const;
  23. 	UBigInt operator /(const UBigInt& dsr) const;
  24. 	UBigInt operator %(const UBigInt& nrm) const;
  25. 	UBigInt operator <<(const size_t& wid) const;
  26. 	UBigInt operator >>(const size_t& wid) const;
  27. 	UBigInt& operator =(const UBigInt& num);
  28. 	UBigInt& operator +=(const UBigInt& ade);
  29. 	UBigInt& operator -=(const UBigInt& sub);
  30. 	UBigInt& operator *=(const UBigInt& mer);
  31. 	UBigInt& operator /=(const UBigInt& dsr);
  32. 	UBigInt& operator %=(const UBigInt& nrm);
  33. 	UBigInt& operator <<=(const size_t& wid);
  34. 	UBigInt& operator >>=(const size_t& wid);
  35. 	UBigInt& operator ++();
  36. 	UBigInt operator ++(int);
  37. 	UBigInt& operator --();
  38. 	UBigInt operator --(int);
  39. 	bool operator ==(const UBigInt& num) const;
  40. 	bool operator <(const UBigInt& num) const;
  41. 	bool operator >(const UBigInt& num) const;
  42. 	bool operator !=(const UBigInt& num) const;
  43. 	bool operator <=(const UBigInt& num) const;
  44. 	bool operator >=(const UBigInt& num) const;
  45. 	UBigInt power(const UBigInt& exp);
  46. 	UBigInt modPower(const UBigInt& exp, const UBigInt& nrm);
  47. 	void powerAssign(const UBigInt& exp);
  48. 	void modPowerAssign(const UBigInt& exp, const UBigInt& nrm);
  49. 	bool isZero() const;
  50. 	bool getLowestBit() const;
  51. 	unsigned long getLowestDWord() const;
  52. 	string toString(const unsigned int& base = 10) const;
  53. 	static UBigInt fromString(const string& str, const unsigned int& base = 10);
  54. protected:
  55. 	shared_ptr<vector<bool> > bits;
  56. 	static shared_ptr<vector<bool> > makeBits(const unsigned long& val);
  57. 	static shared_ptr<vector<bool> > add(const shared_ptr<vector<bool> >& age, const shared_ptr<vector<bool> >& ade);
  58. 	static shared_ptr<vector<bool> > subtract(const shared_ptr<vector<bool> >& min, const shared_ptr<vector<bool> >& sub);
  59. 	static shared_ptr<vector<bool> > multiply(const shared_ptr<vector<bool> >& mca, const shared_ptr<vector<bool> >& mer);
  60. 	static shared_ptr<vector<bool> > divide(const shared_ptr<vector<bool> >& dde, const shared_ptr<vector<bool> >& dsr, shared_ptr<vector<bool> >* rem = NULL);
  61. 	static shared_ptr<vector<bool> > leftShift(const shared_ptr<vector<bool> >& bits, const size_t& wid);
  62. 	static shared_ptr<vector<bool> > rightShift(const shared_ptr<vector<bool> >& bits, const size_t& wid);
  63. 	static bool less(const shared_ptr<vector<bool> >& left, const shared_ptr<vector<bool> >& right);
  64. 	static bool equal(const shared_ptr<vector<bool> >& left, const shared_ptr<vector<bool> >& right);
  65. 	static bool isZero(const shared_ptr<vector<bool> >& bits);
  66. 	static unsigned long getLowestDWord(const shared_ptr<vector<bool> >& bits);
  67. 	static unsigned int charToFigure(const char& ch);
  68. 	static char figureToChar(const unsigned int& fig);
  69. 	static shared_ptr<vector<bool> > trim(const shared_ptr<vector<bool> >& bits);
  70. };
  71.  
  72. #define ASSERT(pred) assert(#pred, pred);
  73.  
  74. extern void assert(const char* pred_str, const bool& pred);
  75.  
  76. bool primalityTestMillerRabin(const UBigInt& p, const unsigned long& cnt) {
  77. 	bool res;
  78. 	if (p == 1UL) res = false;
  79. 	else if (p == 2UL) res = true;
  80. 	else if (p.getLowestBit() == false) res = false;
  81. 	else {
  82. 		UBigInt q = p - 1UL;
  83. 		UBigInt k(true);
  84. 		while (q.getLowestBit() == false) {
  85. 			q >>= 1;
  86. 			k++;
  87. 		}
  88. 		UBigInt a(2UL);
  89. 		UBigInt gap(((p - 1UL) - 2UL) / cnt);
  90. 		if (gap.isZero()) gap++;
  91. 		for (; a < p; a += gap) {
  92. 			UBigInt b = a.modPower(q, p);
  93. 			if (b != 1UL && b != p - 1UL) {
  94. 				UBigInt i(1UL);
  95. 				for (; i < k; i++) {
  96. 					b = (b * b) % p;
  97. 					if (b == 1UL || b == p - 1UL) break;
  98. 				}
  99. 				if (i == k) {
  100. 					res = false;
  101. 					break;
  102. 				}
  103. 			}
  104. 		}
  105. 		if (a >= p) res = true;
  106. 	}
  107. 	return res;
  108. }
  109.  
  110. UBigInt::UBigInt(const bool& bit) : bits(new vector<bool>(1, bit)) {}
  111.  
  112. UBigInt::UBigInt(const shared_ptr<vector<bool> >& bits) : bits(bits) {}
  113.  
  114. UBigInt::UBigInt(const unsigned long& val) : bits(makeBits(val)) {}
  115.  
  116. UBigInt::UBigInt(const UBigInt& num) : bits(new vector<bool>(*num.bits)) {}
  117.  
  118. UBigInt UBigInt::operator +(const UBigInt& ade) const {
  119. 	return UBigInt(add(this->bits, ade.bits));
  120. }
  121.  
  122. UBigInt UBigInt::operator -(const UBigInt& sub) const {
  123. 	return UBigInt(subtract(this->bits, sub.bits));
  124. }
  125.  
  126. UBigInt UBigInt::operator *(const UBigInt& mer) const {
  127. 	return UBigInt(multiply(this->bits, mer.bits));
  128. }
  129.  
  130. UBigInt UBigInt::operator /(const UBigInt& dsr) const {
  131. 	return UBigInt(divide(this->bits, dsr.bits));
  132. }
  133.  
  134. UBigInt UBigInt::operator %(const UBigInt& nrm) const {
  135. 	shared_ptr<vector<bool> > rem;
  136. 	divide(this->bits, nrm.bits, &rem);
  137. 	return UBigInt(rem);
  138. }
  139.  
  140. UBigInt UBigInt::operator <<(const size_t& wid) const {
  141. 	return UBigInt(leftShift(this->bits, wid));
  142. }
  143.  
  144. UBigInt UBigInt::operator >>(const size_t& wid) const {
  145. 	return UBigInt(rightShift(this->bits, wid));
  146. }
  147.  
  148. UBigInt& UBigInt::operator =(const UBigInt& num) {
  149. 	this->bits = shared_ptr<vector<bool> >(new vector<bool>(*num.bits));
  150. 	return *this;
  151. }
  152.  
  153. UBigInt& UBigInt::operator +=(const UBigInt& add) {
  154. 	return *this = *this + add;
  155. }
  156.  
  157. UBigInt& UBigInt::operator -=(const UBigInt& sub) {
  158. 	return *this = *this - sub;
  159. }
  160.  
  161. UBigInt& UBigInt::operator *=(const UBigInt& mer) {
  162. 	return *this = *this * mer;
  163. }
  164.  
  165. UBigInt& UBigInt::operator /=(const UBigInt& dsr) {
  166. 	return *this = *this / dsr;
  167. }
  168.  
  169. UBigInt& UBigInt::operator %=(const UBigInt& nrm) {
  170. 	return *this = *this % nrm;
  171. }
  172.  
  173. UBigInt& UBigInt::operator <<=(const size_t& wid) {
  174. 	return *this = *this << wid;
  175. }
  176.  
  177. UBigInt& UBigInt::operator >>=(const size_t& wid) {
  178. 	return *this = *this >> wid;
  179. }
  180.  
  181. UBigInt& UBigInt::operator ++() {
  182. 	return *this += UBigInt(true);
  183. }
  184.  
  185. UBigInt UBigInt::operator ++(int) {
  186. 	UBigInt res = *this;
  187. 	*this += UBigInt(true);
  188. 	return res;
  189. }
  190.  
  191. UBigInt& UBigInt::operator --() {
  192. 	return *this -= UBigInt(true);
  193. }
  194.  
  195. UBigInt UBigInt::operator --(int) {
  196. 	UBigInt res = *this;
  197. 	*this -= UBigInt(true);
  198. 	return res;
  199. }
  200.  
  201. bool UBigInt::operator ==(const UBigInt& num) const {
  202. 	return equal(this->bits, num.bits);
  203. }
  204.  
  205. bool UBigInt::operator <(const UBigInt& num) const {
  206. 	return less(this->bits, num.bits);
  207. }
  208.  
  209. bool UBigInt::operator >(const UBigInt& num) const {
  210. 	return !equal(this->bits, num.bits) && !less(this->bits, num.bits);
  211. }
  212.  
  213. bool UBigInt::operator !=(const UBigInt& num) const {
  214. 	return !equal(this->bits, num.bits);
  215. }
  216.  
  217. bool UBigInt::operator <=(const UBigInt& num) const {
  218. 	return equal(this->bits, num.bits) || less(this->bits, num.bits);
  219. }
  220.  
  221. bool UBigInt::operator >=(const UBigInt& num) const {
  222. 	return !less(this->bits, num.bits);
  223. }
  224.  
  225. UBigInt UBigInt::power(const UBigInt& exp) {
  226. 	if (isZero()) return UBigInt(false);
  227. 	UBigInt res(true);
  228. 	UBigInt coef = *this;
  229. 	for (UBigInt exp2 = exp;;) {
  230. 		if (exp2.getLowestBit()) {
  231. 			res *= coef;
  232. 		}
  233. 		exp2 >>= 1;
  234. 		if (exp2.isZero()) break;
  235. 		coef *= coef;
  236. 	}
  237. 	return res;
  238. }
  239.  
  240. UBigInt UBigInt::modPower(const UBigInt& exp, const UBigInt& nrm) {
  241. 	if (nrm.isZero()) throw string("法がゼロ。");
  242. 	if (isZero()) return UBigInt(false);
  243. 	UBigInt res(true);
  244. 	UBigInt coef = *this % nrm;
  245. 	for (UBigInt exp2 = exp;;) {
  246. 		if (exp2.getLowestBit()) {
  247. 			res = (res * coef) % nrm;
  248. 		}
  249. 		exp2 >>= 1;
  250. 		if (exp2.isZero()) break;
  251. 		coef = (coef * coef) % nrm;
  252. 	}
  253. 	return res;
  254. }
  255.  
  256. void UBigInt::powerAssign(const UBigInt& exp) {
  257. 	*this = power(exp);
  258. }
  259.  
  260. void UBigInt::modPowerAssign(const UBigInt& exp, const UBigInt& nrm) {
  261. 	*this = modPower(exp, nrm);
  262. }
  263.  
  264. bool UBigInt::isZero() const {
  265. 	return isZero(this->bits);
  266. }
  267.  
  268. bool UBigInt::getLowestBit() const {
  269. 	return this->bits->back();
  270. }
  271.  
  272. unsigned long UBigInt::getLowestDWord() const {
  273. 	return getLowestDWord(this->bits);
  274. }
  275.  
  276. string UBigInt::toString(const unsigned int& base) const {
  277. 	string res;
  278. 	shared_ptr<vector<bool> > wrk = this->bits;
  279. 	shared_ptr<vector<bool> > base_bits(makeBits(base));
  280. 	while (!isZero(wrk)) {
  281. 		shared_ptr<vector<bool> > rem;
  282. 		wrk = divide(wrk, base_bits, &rem);
  283. 		res += figureToChar(getLowestDWord(rem));
  284. 	}
  285. 	if (res.empty()) res += '0';
  286. 	reverse(res.begin(), res.end());
  287. 	return res;
  288. }
  289.  
  290. UBigInt UBigInt::fromString(const string& str, const unsigned int& base) {
  291. 	shared_ptr<vector<bool> > bits(new vector<bool>(1, false));
  292. 	shared_ptr<vector<bool> > base_bits(makeBits(base));
  293. 	for (string::const_iterator iter = str.begin(); iter != str.end(); iter++) {
  294. 		if (iter != str.begin()) bits = multiply(bits, base_bits);
  295. 		unsigned int fig = charToFigure(*iter);
  296. 		if (fig >= base) throw string("値が範囲を逸脱している。");
  297. 		bits = add(bits, makeBits(fig));
  298. 	}
  299. 	return UBigInt(bits);
  300. }
  301.  
  302. shared_ptr<vector<bool> > UBigInt::makeBits(const unsigned long& val) {
  303. 	shared_ptr<vector<bool> > res(new vector<bool>);
  304. 	for (int i = 31; i >= 0; i--) {
  305. 		if ((val >> i) & 1) res->push_back(true);
  306. 		else if (!res->empty()) res->push_back(false);
  307. 	}
  308. 	if (res->empty()) res->push_back(false);
  309. 	return res;
  310. }
  311.  
  312. shared_ptr<vector<bool> > UBigInt::add(const shared_ptr<vector<bool> >& age, const shared_ptr<vector<bool> >& ade) {
  313. 	shared_ptr<vector<bool> > sum(new vector<bool>);
  314. 	vector<bool>::const_reverse_iterator age_iter = age->rbegin();
  315. 	vector<bool>::const_reverse_iterator ade_iter = ade->rbegin();
  316. 	bool carry = false;
  317. 	while (age_iter != age->rend() || ade_iter != ade->rend()) {
  318. 		int age_val = age_iter != age->rend() ? int(*age_iter) : 0;
  319. 		int ade_val = ade_iter != ade->rend() ? int(*ade_iter) : 0;
  320. 		int sum_val = age_val + ade_val + int(carry);
  321. 		carry = sum_val > 1;
  322. 		if (carry) sum_val -= 2;
  323. 		sum->push_back(sum_val == 1);
  324. 		if (age_iter != age->rend()) age_iter++;
  325. 		if (ade_iter != ade->rend()) ade_iter++;
  326. 	}
  327. 	if (carry) sum->push_back(true);
  328. 	if (sum->empty()) sum->push_back(false);
  329. 	reverse(sum->begin(), sum->end());
  330. 	return sum;
  331. }
  332.  
  333. shared_ptr<vector<bool> > UBigInt::subtract(const shared_ptr<vector<bool> >& min, const shared_ptr<vector<bool> >& sub) {
  334. 	shared_ptr<vector<bool> > dif(new vector<bool>);
  335. 	vector<bool>::const_reverse_iterator min_iter = min->rbegin();
  336. 	vector<bool>::const_reverse_iterator sub_iter = sub->rbegin();
  337. 	bool borrow = false;
  338. 	while (min_iter != min->rend() || sub_iter != sub->rend()) {
  339. 		int min_val = min_iter != min->rend() ? int(*min_iter) : 0;
  340. 		int sub_val = sub_iter != sub->rend() ? int(*sub_iter) : 0;
  341. 		int dif_val = min_val - sub_val - int(borrow);
  342. 		borrow = dif_val < 0;
  343. 		if (borrow) dif_val += 2;
  344. 		dif->push_back(dif_val == 1);
  345. 		if (min_iter != min->rend()) min_iter++;
  346. 		if (sub_iter != sub->rend()) sub_iter++;
  347. 	}
  348. 	if (borrow) throw string("被減数が減数より小さい。");
  349. 	reverse(dif->begin(), dif->end());
  350. 	return trim(dif);
  351. }
  352.  
  353. shared_ptr<vector<bool> > UBigInt::multiply(const shared_ptr<vector<bool> >& mca, const shared_ptr<vector<bool> >& mer) {
  354. 	shared_ptr<vector<bool> > pro(new vector<bool>(1, false));
  355. 	vector<bool>::const_reverse_iterator mer_iter = mer->rbegin();
  356. 	size_t wid = 0;
  357. 	while (mer_iter != mer->rend()) {
  358. 		if (*mer_iter) pro = add(pro, leftShift(mca, wid));
  359. 		mer_iter++;
  360. 		wid++;
  361. 	}
  362. 	return pro;
  363. }
  364.  
  365. shared_ptr<vector<bool> > UBigInt::divide(const shared_ptr<vector<bool> >& dde, const shared_ptr<vector<bool> >& dsr, shared_ptr<vector<bool> >* rem) {
  366. 	if (isZero(dsr)) throw string("除数がゼロ。");
  367. 	shared_ptr<vector<bool> > quo(new vector<bool>);
  368. 	shared_ptr<vector<bool> > fld(new vector<bool>);
  369. 	for (vector<bool>::const_iterator dde_iter = dde->begin(); dde_iter != dde->end(); dde_iter++) {
  370. 		fld->push_back(*dde_iter);
  371. 		fld = trim(fld);
  372. 		if (!less(fld, dsr)) {
  373. 			quo->push_back(true);
  374. 			fld = subtract(fld, dsr);
  375. 		}
  376. 		else if (!quo->empty()) quo->push_back(false);
  377. 	}
  378. 	if (quo->empty()) quo->push_back(false);
  379. 	if (rem) *rem = fld;
  380. 	return quo;
  381. }
  382.  
  383. shared_ptr<vector<bool> > UBigInt::leftShift(const shared_ptr<vector<bool> >& bits, const size_t& wid) {
  384. 	shared_ptr<vector<bool> > res(new vector<bool>(*bits));
  385. 	for (int i = 0; i < wid; i++) res->push_back(false);
  386. 	return res;
  387. }
  388.  
  389. shared_ptr<vector<bool> > UBigInt::rightShift(const shared_ptr<vector<bool> >& bits, const size_t& wid) {
  390. 	shared_ptr<vector<bool> > res;
  391. 	if (wid < bits->size()) res = shared_ptr<vector<bool> >(new vector<bool>(bits->begin(), bits->end() - wid));
  392. 	else res = shared_ptr<vector<bool> >(new vector<bool>(1, false));
  393. 	return res;
  394. }
  395.  
  396. bool UBigInt::equal(const shared_ptr<vector<bool> >& left, const shared_ptr<vector<bool> >& right) {
  397. 	bool res;
  398. 	if (left->size() != right->size()) res = false;
  399. 	else {
  400. 		vector<bool>::const_iterator left_iter = left->begin();
  401. 		vector<bool>::const_iterator right_iter = right->begin();
  402. 		for (;;) {
  403. 			if (left_iter == left->end()) {
  404. 				res = true;
  405. 				break;
  406. 			}
  407. 			else if (!*left_iter && *right_iter) {
  408. 				res = false;
  409. 				break;
  410. 			}
  411. 			else if (*left_iter && !*right_iter) {
  412. 				res = false;
  413. 				break;
  414. 			}
  415. 			left_iter++;
  416. 			right_iter++;
  417. 		}
  418. 	}
  419. 	return res;
  420. }
  421.  
  422. bool UBigInt::less(const shared_ptr<vector<bool> >& left, const shared_ptr<vector<bool> >& right) {
  423. 	bool res;
  424. 	if (left->size() < right->size()) res = true;
  425. 	else if (left->size() > right->size()) res = false;
  426. 	else {
  427. 		vector<bool>::const_iterator left_iter = left->begin();
  428. 		vector<bool>::const_iterator right_iter = right->begin();
  429. 		for (;;) {
  430. 			if (left_iter == left->end()) {
  431. 				res = false;
  432. 				break;
  433. 			}
  434. 			else if (!*left_iter && *right_iter) {
  435. 				res = true;
  436. 				break;
  437. 			}
  438. 			else if (*left_iter && !*right_iter) {
  439. 				res = false;
  440. 				break;
  441. 			}
  442. 			left_iter++;
  443. 			right_iter++;
  444. 		}
  445. 	}
  446. 	return res;
  447. }
  448.  
  449. bool UBigInt::isZero(const shared_ptr<vector<bool> >& bits) {
  450. 	return bits->size() == 1 && bits->front() == false;
  451. }
  452.  
  453. unsigned long UBigInt::getLowestDWord(const shared_ptr<vector<bool> >& bits) {
  454. 	unsigned long res = 0;
  455. 	vector<bool>::const_iterator iter = bits->begin();
  456. 	for (int i = 0; i < 32; i++) {
  457. 		if (iter == bits->end()) break;
  458. 		if (i != 0) res <<= 1;
  459. 		res |= int(*iter);
  460. 		iter++;
  461. 	}
  462. 	return res;
  463. }
  464.  
  465. unsigned int UBigInt::charToFigure(const char& ch) {
  466. 	unsigned int res;
  467. 	if (ch >= '0' && ch <= '9') res = ch - '0';
  468. 	else if (ch >= 'A' && ch <= 'Z') res = 10 + ch - 'A';
  469. 	else if (ch >= 'a' && ch <= 'z') res = 10 + ch - 'a';
  470. 	else throw string("文字が数ではない。");
  471. 	return res;
  472. }
  473.  
  474. char UBigInt::figureToChar(const unsigned int& fig) {
  475. 	char res;
  476. 	if (fig >= 0 && fig <= 9) res = '0' + fig;
  477. 	else if (fig >= 10 && fig <= 36) res = 'A' + (fig - 10);
  478. 	else throw string("値が範囲を逸脱している。");
  479. 	return res;
  480. }
  481.  
  482. shared_ptr<vector<bool> > UBigInt::trim(const shared_ptr<vector<bool> >& bits) {
  483. 	size_t pos = 0;
  484. 	while (pos != bits->size() && bits->at(pos) == false) pos++;
  485. 	if (pos == bits->size()) pos--;
  486. 	return shared_ptr<vector<bool> >(new vector<bool>(bits->begin() + pos, bits->end()));
  487. }
  488.  
  489. void assert(const char* pred_str, const bool& pred) {
  490. 	if (pred) {
  491. 		cout << "アサート成功: " << pred_str << endl;
  492. 	}
  493. 	else {
  494. 		cerr << "アサート失敗: " << pred_str << endl;
  495. 		exit(1);
  496. 	}
  497. }
  498.  
  499. int main() {
  500. 	try {
  501. 		ASSERT(primalityTestMillerRabin(UBigInt::fromString("0")) == false)
  502. 		ASSERT(primalityTestMillerRabin(UBigInt::fromString("1")) == false)
  503. 		ASSERT(primalityTestMillerRabin(UBigInt::fromString("2")) == true)
  504. 		ASSERT(primalityTestMillerRabin(UBigInt::fromString("3")) == true)
  505. 		ASSERT(primalityTestMillerRabin(UBigInt::fromString("4")) == false)
  506. 		ASSERT(primalityTestMillerRabin(UBigInt::fromString("5")) == true)
  507. 		ASSERT(primalityTestMillerRabin(UBigInt::fromString("6")) == false)
  508. 		ASSERT(primalityTestMillerRabin(UBigInt::fromString("7")) == true)
  509. 		ASSERT(primalityTestMillerRabin(UBigInt::fromString("8")) == false)
  510. 		ASSERT(primalityTestMillerRabin(UBigInt::fromString("9")) == false)
  511. 		ASSERT(primalityTestMillerRabin(UBigInt::fromString("87")) == false)
  512. 		ASSERT(primalityTestMillerRabin(UBigInt::fromString("89")) == true)
  513. 		ASSERT(primalityTestMillerRabin(UBigInt::fromString("329")) == false)
  514. 		ASSERT(primalityTestMillerRabin(UBigInt::fromString("331")) == true)
  515. 		ASSERT(primalityTestMillerRabin(UBigInt::fromString("561")) == false)
  516. 		ASSERT(primalityTestMillerRabin(UBigInt::fromString("563")) == true)
  517. 		ASSERT(primalityTestMillerRabin(UBigInt::fromString("807")) == false)
  518. 		ASSERT(primalityTestMillerRabin(UBigInt::fromString("809")) == true)
  519. 		ASSERT(primalityTestMillerRabin(UBigInt::fromString("2251")) == true)
  520. //		ASSERT(primalityTestMillerRabin(UBigInt::fromString("59561")) == true)
  521. //		ASSERT(primalityTestMillerRabin(UBigInt::fromString("181243")) == true)
  522. //		ASSERT(primalityTestMillerRabin(UBigInt::fromString("14414443")) == true)
  523. 	}
  524. 	catch (const string& msg) {
  525. 		cerr << msg << endl;
  526. 		return 1;
  527. 	}
  528. 	return 0;
  529. }
  530.  
Success #stdin #stdout 0.09s 3024KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
アサート成功: primalityTestMillerRabin(UBigInt::fromString("0")) == false
アサート成功: primalityTestMillerRabin(UBigInt::fromString("1")) == false
アサート成功: primalityTestMillerRabin(UBigInt::fromString("2")) == true
アサート成功: primalityTestMillerRabin(UBigInt::fromString("3")) == true
アサート成功: primalityTestMillerRabin(UBigInt::fromString("4")) == false
アサート成功: primalityTestMillerRabin(UBigInt::fromString("5")) == true
アサート成功: primalityTestMillerRabin(UBigInt::fromString("6")) == false
アサート成功: primalityTestMillerRabin(UBigInt::fromString("7")) == true
アサート成功: primalityTestMillerRabin(UBigInt::fromString("8")) == false
アサート成功: primalityTestMillerRabin(UBigInt::fromString("9")) == false
アサート成功: primalityTestMillerRabin(UBigInt::fromString("87")) == false
アサート成功: primalityTestMillerRabin(UBigInt::fromString("89")) == true
アサート成功: primalityTestMillerRabin(UBigInt::fromString("329")) == false
アサート成功: primalityTestMillerRabin(UBigInt::fromString("331")) == true
アサート成功: primalityTestMillerRabin(UBigInt::fromString("561")) == false
アサート成功: primalityTestMillerRabin(UBigInt::fromString("563")) == true
アサート成功: primalityTestMillerRabin(UBigInt::fromString("807")) == false
アサート成功: primalityTestMillerRabin(UBigInt::fromString("809")) == true
アサート成功: primalityTestMillerRabin(UBigInt::fromString("2251")) == true
https://ideone.com/yGy27K
language:
C++14 (gcc 8.3)
created:
11 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!