Ачат -- Форум математиков

ага, невнимательный, тогда вот так:

Code:

#!/usr/bin/perl
$nn=19; # Ваше число, которое надо разложить на сумму взаимно простых чисел
$nnn=4; # Минимальное кол-во слагаемых
for(my $i=2;$i<$nn; $i++){
  push(@pers,$i);
}
sub gcd
{
  my @xx=@_;$size = @xx; 
  for($i=0;$i<$size;$i++){
     $x=$xx[$i]; $y=$xx[$i+1];
     while($x){
      ($x, $y)=($y, $x) if $x>$y;
      $y-=$x;
     }
     return $y;
  }
}
print "\nAll simple numbers in $nn: [@pers] \n";
$size = @pers;
crack($size);
sub crack{
 $| = 1;
 $CharSet = shift;
 @RawString = ();
 for (my $i =0;$i<$CharSet;$i++){ $RawString[i] = 0;}
 do{
  for (my $i =0;$i<$CharSet;$i++){
   if ($RawString[$i] > $size){
    if ($i==$CharSet-1){
    $cnt=0;
    return false;
   }
   $RawString[$i+1]++;
   $RawString[$i]=0;
   }
  }
   $ret = "";
   $ret1 = 0;
   for (my $i=0;$i<$CharSet;$i++){ 
         $my=length($pers[$i]);  
         $ret = $ret."+".substr($pers[$i],$RawString[$i],$my);
         @pers1 = split /\+/,$ret;@pers1 = grep {$_} @pers1;@pers1=grep{$_!=1} @pers1;$size1=@pers1;
 	if($size1==$nnn){$gcd=gcd(@pers1)}
         print "Variants: $cnt\r";
         $ret1 = $ret1+substr($pers[$i],$RawString[$i],$my);
         #print "@pers1\n";
         if($ret1==$nn && $size1==$nnn && $gcd==1){
           print "\n\n===> @pers1\n";
           exit; 
         }  
   }
   $cnt++;
   $RawString[0]++;
 }while($RawString[$CharSet-1]<$size);
}

PS: пришлось писать алгортим Евклида для массива

PPSS: мать, только сейчас увидел для "9-15 знаков" )) В пень

 

Code:

#include <iostream>

using namespace std;

__int64 gcd(__int64 a, __int64 b)
{
    if ( a == b ) return -1;
    while( 1 )
    {
        a = a % b;
		if ( a == 0 ) return b;
		b = b % a;
        if( b == 0 ) return a;
    }
}

int main()
{
    __int64 a, b, c, d;
    __int64 x = 100000700000666;
    int p = 100;

    for ( a = x / 4; a > x / 4 - p; a-- )
    {
        for ( b = x / 4; b > x / 4 - p; b-- )
        {
            if ( gcd(a,b) != 1) continue;
            for ( c = x / 4; c > x / 4 - p; c--)
            {
                if ( gcd(a,c) != 1) continue;
                if ( gcd(b,c) != 1) continue;
                d = x - a - b - c;
                if ( gcd(a,d) != 1) continue;
                if ( gcd(b,d) != 1) continue;
                if ( gcd(c,d) != 1) continue;
                cout << a << endl << b << endl << c << endl << d << endl;
                return 0;
            }
        }
    }
}

Проверка: тыц тыц тыц тыц тыц тыц