fork download
copy 
  1. #!/usr/bin/perl6
  2. # your code goes here
  3. sub prime-factors ( Int $n where * > 0 ) {
  4.     return $n if $n.is-prime;
  5.     return () if $n == 1;
  6.     my $factor = find-factor( $n );
  7.     sort flat ( $factor, $n div $factor ).map: &prime-factors;
  8. }
  9.  
  10. sub find-factor ( Int $n, $constant = 1 ) {
  11.     return 2 unless $n +& 1;
  12.     if (my $gcd = $n gcd 6541380665835015) > 1 { # magic number: [*] primes 3 .. 43
  13.         return $gcd if $gcd != $n
  14.     }
  15.     my $x      = 2;
  16.     my $rho    = 1;
  17.     my $factor = 1;
  18.     while $factor == 1 {
  19.         $rho = $rho +< 1;
  20.         my $fixed = $x;
  21.         my int $i = 0;
  22.         while $i < $rho {
  23.             $x = ( $x * $x + $constant ) % $n;
  24.             $factor = ( $x - $fixed ) gcd $n;
  25.             last if 1 < $factor;
  26.             $i = $i + 1;
  27.         }
  28.     }
  29.     $factor = find-factor( $n, $constant + 1 ) if $n == $factor;
  30.     $factor;
  31. }
  32.  
  33.  
  34.  my $now = now;
  35. .put for (2..100).grep( &is-prime).hyper(:4batch).map: { "2**$_ - 1: ", (2**$_-1).&prime-factors.join('×')} ;
  36. .put for (600851475143, 100000000000000000037).map: { $_, .&prime-factors.join('×')} ;
  37. say now - $now;
Success #stdin #stdout 1.07s 185872KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
2**2 - 1:  3
2**3 - 1:  7
2**5 - 1:  31
2**7 - 1:  127
2**11 - 1:  23×89
2**13 - 1:  8191
2**17 - 1:  131071
2**19 - 1:  524287
2**23 - 1:  47×178481
2**29 - 1:  233×1103×2089
2**31 - 1:  2147483647
2**37 - 1:  223×616318177
2**41 - 1:  13367×164511353
2**43 - 1:  431×9719×2099863
2**47 - 1:  2351×4513×13264529
2**53 - 1:  6361×69431×20394401
2**59 - 1:  179951×3203431780337
2**61 - 1:  2305843009213693951
2**67 - 1:  193707721×761838257287
2**71 - 1:  228479×48544121×212885833
2**73 - 1:  439×2298041×9361973132609
2**79 - 1:  2687×202029703×1113491139767
2**83 - 1:  167×57912614113275649087721
2**89 - 1:  618970019642690137449562111
2**97 - 1:  11447×13842607235828485645766393
600851475143 71×839×1471×6857
100000000000000000037 31×821×59004541×66590107
0.785447
https://ideone.com/9kLSh4
language:
Perl (perl 2018.12)
created:
2 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!