123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157 |
- #!/usr/bin/perl
- # Author: Daniel "Trizen" Șuteu
- # License: GPLv3
- # Date: 10 July 2015
- # Website: https://github.com/trizen
- # Generate a Perl program to compute the prime factors of a semiprime number.
- use 5.016;
- use strict;
- use integer;
- use warnings;
- sub semiprime_equationization {
- my ($semiprime, $xlen, $ylen) = @_;
- $xlen -= 1;
- $ylen -= 1;
- my @map;
- my @result;
- my $mem = '0';
- my %x_loops;
- foreach my $i (0 .. $xlen) {
- my $start = $i == $xlen ? 1 : 0;
- if ($i == 0) {
- $x_loops{"x$i"} = "for (my \$x$i = 1; \$x$i < 10; \$x$i += 2) {";
- }
- else {
- $x_loops{"x$i"} = "for my \$x$i ($start .. 9) {";
- }
- }
- my %y_loops;
- foreach my $i (0 .. $ylen) {
- my $start = $i == $ylen ? 1 : 0;
- if ($i == 0) {
- $y_loops{"y$i"} = "for (my \$y$i = 1; \$y$i < 10; \$y$i += 2) {";
- }
- else {
- $y_loops{"y$i"} = "for my \$y$i ($start .. 9) {";
- }
- }
- my %vars;
- foreach my $j (0 .. $ylen) {
- foreach my $i (0 .. $xlen) {
- my $expr = '(' . join(' + ', "(\$x$i * \$y$j)", grep { $_ ne '0' } $mem) . ')';
- $vars{"xy$i$j"} = $expr;
- my $n = "\$xy$i$j";
- if ($i == $xlen) {
- push @{$map[$j]}, "($n % 10)", "($n / 10)";
- $mem = '0';
- }
- else {
- push @{$map[$j]}, "($n % 10)";
- $mem = "($n / 10)";
- }
- }
- my $n = $ylen - $j;
- if ($n > 0) {
- push @{$map[$j]}, ((0) x $n);
- }
- my $m = $ylen - $n;
- if ($m > 0) {
- unshift @{$map[$j]}, ((0) x $m);
- }
- }
- my @number = reverse split //, $semiprime;
- my @mrange = (0 .. $#map);
- my $end = $xlen + $ylen + 1;
- my %seen;
- my $loop_init = sub {
- my ($str) = @_;
- while ($str =~ /\$(y\d+)/g) {
- if (not $seen{$1}++) {
- my $init = $y_loops{$1};
- push @result, $init;
- }
- }
- while ($str =~ /\$(x\d+)/g) {
- if (not $seen{$1}++) {
- my $init = $x_loops{$1};
- push @result, $init;
- }
- }
- };
- my $initializer = sub {
- my ($str) = @_;
- $loop_init->($str);
- while ($str =~ /\$(xy\d+)/g) {
- if (not $seen{$1}++) {
- my $init = "my \$$1 = $vars{$1};";
- __SUB__->($init);
- push @result, $init;
- }
- }
- };
- foreach my $i (0 .. $#number) {
- my $expr = '(' . join(' + ', grep { $_ ne '0' } (map { $map[$_][$i] } @mrange), $mem) . ')';
- $initializer->($expr);
- push @result, "my \$n$i = $expr;";
- my $n = "\$n$i";
- if ($i == $#number) {
- push @result,
- qq/if ($number[$i] == $n) { printf("Cracked: /
- . ("%d" x ($xlen + 1))
- . (" * ")
- . ("%d" x ($ylen + 1))
- . qq/\\n", /
- . join(", ", (map { "\$x$_" } reverse(0 .. $xlen)), (map { "\$y$_" } reverse(0 .. $ylen)))
- . qq/); exit 0; }/;
- }
- elsif ($i == 0) {
- push @result, "if ($number[$i] == $n) {";
- $mem = '0';
- }
- else {
- push @result, "if ($number[$i] == ($n % 10)) {";
- $mem = "($n / 10)";
- }
- }
- unshift @result, ('use integer;', 'use strict;', 'use warnings;');
- push @result, "}" x (1 + $xlen + 1 + $ylen + $#number);
- return @result;
- }
- # 71 * 43
- #say for semiprime_equationization('3053', 2, 2);
- # 251 * 197
- #say for semiprime_equationization('49447', 3, 3);
- # 7907 * 4999
- say for semiprime_equationization('39527093', 4, 4);
- # 472882049 * 472882049
- #say for semiprime_equationization('223617432266438401', 9, 9);
- # 37975227936943673922808872755445627854565536638199 * 40094690950920881030683735292761468389214899724061
- #say for semiprime_equationization('1522605027922533360535618378132637429718068114961380688657908494580122963258952897654000350692006139', 50, 50);
|