Advertisement
HwapX

Lowest prime palindrome greater than time

Sep 7th, 2015
133
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <stdio.h>
  2. #include <math.h>
  3. #include <time.h>
  4. #include <windows.h>
  5.  
  6. typedef time_t prime_t;
  7.  
  8. prime_t reverseDigits(prime_t num)
  9. {
  10.     prime_t rev_num = 0;
  11.     while(num > 0)
  12.     {
  13.         rev_num = rev_num * 10 + (num % 10);
  14.         num = num * 0.1;
  15.     }
  16.     return rev_num;
  17. }
  18.  
  19. prime_t nextPalindrome(prime_t n) {
  20.     n++;
  21.     int digits = 0;
  22.     prime_t num = n;
  23.     do {
  24.         digits++;
  25.     } while((num *= 0.1) > 0);
  26.        
  27.     prime_t half = digits * 0.5;
  28.     prime_t left = n * pow(0.1, half);
  29.     prime_t r_left = reverseDigits(left);
  30.     if(r_left % 2 == 0) {
  31.         return nextPalindrome(((int)(n * pow(0.1, digits-1)) + 1) * pow(10, digits-1));
  32.         r_left = reverseDigits(left);
  33.     }
  34.     prime_t p10h  = pow(10, half);
  35.     prime_t right = n - (left * p10h);
  36.  
  37.     if(digits % 10) {
  38.         r_left = reverseDigits(left * 0.1);
  39.        
  40.         if(r_left > right)
  41.             return (left * p10h) + r_left;
  42.         else {
  43.             ++left;
  44.             return (left * p10h) + reverseDigits(left * 0.1);
  45.         }
  46.     } else {
  47.         if(r_left > right)
  48.             return (left * p10h) + r_left;
  49.         else {
  50.             ++left;
  51.             return (left * p10h) + reverseDigits(left);
  52.         }
  53.     }
  54. }
  55.  
  56. int isPrime(prime_t n) {
  57.     prime_t i;
  58.            
  59.     if(n == 2)
  60.         return 1;
  61.     else if (n == 3)
  62.         return 1;
  63.     else if (n * 0.5 == 0)
  64.         return 0;
  65.     else if (n % 3 == 0)
  66.         return 0;
  67.        
  68.     i = 5;
  69.     prime_t c = 2;
  70.     while(i * i < n) {
  71.         if(n % i == 0)
  72.             return 0;
  73.         i += c;
  74.         c = 6 - c;
  75.     }
  76.            
  77.     return 1;
  78. }
  79.  
  80. int main(int argc, char **argv)
  81. {
  82.     time_t t = time(NULL);
  83.     printf("next prime palindrome of %I64u is ", t);
  84.    
  85.     unsigned int s = GetTickCount();
  86.    
  87.     do {
  88.         t = nextPalindrome(t);
  89.     } while(!isPrime(t));
  90.    
  91.     printf("%I64u\n", t);
  92.     printf("elapsed %lu milliseconds", GetTickCount() - s);
  93.     return 0;
  94. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement