Advertisement
thecplusplusguy

bignum library - test2.cpp - find mersenne primes

Jul 6th, 2012
315
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.36 KB | None | 0 0
  1. //a bignum library written in C++, it can (in theory) calculate with 4 billion digit long numbers
  2. //this is mostly for demonstration purposes, if you need performance, use something like GNU arbitrary precision library
  3. //Implemented by: http://www.youtube.com/user/thecplusplusguy
  4. //this might be an older version, I have to check
  5. //this one find the first 50 mersenne prime (LOL, if you have enough time :)
  6. #include <iostream>
  7. #include <fstream>
  8. #include "bignum.h"
  9. #include <string>
  10.  
  11. bool is_prime(int cur)
  12. {
  13.     int tmp=3;
  14. //  std::cout << cur << std::endl;
  15.     while(tmp*tmp<cur)
  16.     {
  17.         if((cur%tmp)==0)
  18.             return false;
  19.         tmp+=2;
  20.     }
  21.     return true;
  22. }
  23.  
  24. void nextprime(int& cur)
  25. {
  26.     if(cur==2)
  27.     {
  28.         cur=3;
  29.         return;
  30.     }
  31.     cur+=2;
  32.     while(!is_prime(cur))
  33.         cur+=2;
  34. }
  35.  
  36. int main()
  37. {
  38.     bignum bn(1);
  39.     bignum tmp;
  40.     bignum tmp2;
  41.     int i=0;
  42.     int j=3;
  43.     int j2=0;
  44.     int diff;
  45.     int mult;
  46.     while(i<50)
  47.     {
  48.         diff=j-j2;
  49.         mult=1;
  50.         mult<<=diff;
  51.         bn*=mult;
  52.         tmp=bn-1;
  53.         tmp2=4;
  54.         std::cout << 2 << " " << 4 << std::endl;    //manually this one
  55.         for(int k=0;k<j-2;k++)
  56.         {
  57. //          std::cout << (tmp2*tmp2) << std::endl;
  58.             tmp2=((tmp2*tmp2)-2)%tmp;
  59. //          std::cout << bn << " " << k << " " << tmp2 << std::endl;
  60.         }
  61.         if(tmp2==0)
  62.         {
  63.             std::cout << j << " " << tmp << std::endl;
  64.             i++;
  65.         }
  66.         j2=j;
  67.         nextprime(j);
  68.        
  69.     }
  70.     std::cout << std::endl;
  71.     return 0;
  72. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement