Serwis Edukacyjny
w I-LO w Tarnowie
obrazek

Materiały dla uczniów liceum

  Wyjście       Spis treści       Wstecz       Dalej  

Autor artykułu: mgr Jerzy Wałaszek

©2020 mgr Jerzy Wałaszek
I LO w Tarnowie

Czynniki pierwsze – metoda Fermata

SPIS TREŚCI
Podrozdziały

Problem

Znaleźć rozkład liczby p  > 1. na iloczyn czynników pierwszych.


Pierre de Fermat podał prosty sposób znajdowania czynników ( liczb dzielących p  bez reszty ) liczby nieparzystej p. Opiera się on na spostrzeżeniu, iż jeśli potrafimy znaleźć dwie liczby naturalne x  i y, takie że:

p  = x 2 - y 2,

to

p  = ( x + y  ) × ( x  - y  ),

zatem czynnikami liczby p  są:

m  = x  + y
n
= x  - y

Znalezione czynniki m  i n  nie muszą być liczbami pierwszymi, zatem metodę Fermata stosujemy również do ich rozkładu. Jest to możliwe, ponieważ czynniki liczby nieparzystej są również nieparzyste. Czynniki 2 można wyeliminować z p  przed zastosowaniem metody Fermata, zatem nie jest to żadne ograniczenie.

Metoda Fermata jest szczególnie efektywna w przypadku czynników leżących w pobliżu pierwiastka z p. W przeciwnym razie jej efektywność jest taka sama lub nawet gorsza jak dla metody próbnych dzieleń. W praktyce metoda Fermata nie jest używana – podajemy ją ze względów dydaktycznych oraz z powodu jej wagi dla innych, bardziej zaawansowanych metod poszukiwań rozkładu liczby na czynniki pierwsze.

Rozwiązanie 1

Algorytm wykorzystuje bezpośrednio własność p  = x 2 - y 2 do znalezienia liczb x  i y. Poszukiwania rozpoczynamy od x  równego pierwiastkowi z p  zaokrąglonemu w górę do najbliższej liczby całkowitej. Obliczamy:

y 2 = x 2 - p

Następnie sprawdzamy, czy y  jest liczbą całkowitą. Jeśli tak, to znaleźliśmy odpowiednie liczby x  i y. Ponieważ liczba p  z założenia jest nieparzysta, to wszystkie jej dzielniki są nieparzyste. Obliczamy dzielniki m  i n  i jeśli są różne od 1, to wywołujemy rekurencyjnie procedurę Fermata do znalezienia ich rozkładu. Jeśli jeden z czynników jest równy 1, to drugi musi być równy p  i p  jest liczbą pierwszą – wypisujemy p  i kończymy.

Ponieważ czynnik musi być mniejszy lub równy p, to:

m  = x  + y  ≤ p

Przy wzroście x  rośnie również y  lub pozostaje takie samo. Zatem gdy suma x  + y  przekroczy p, to nie znajdziemy już żadnego dzielnika liczby p  i algorytm można zakończyć przyjmując, iż p  jest pierwsze.

Algorytm rozkładu liczby naturalnej na czynniki pierwsze metodą Fermata

Wejście:

p  –   liczba rozkładana na czynniki pierwsze, p  ∈ N, p  jest nieparzyste.

Wyjście:

Czynniki pierwsze liczby p.

Zmienne pomocnicze:
x, y, z  –  zmienne do rozkładu p. x, y, z  ∈ N.
m, n  – czynniki p, m, n  ∈ N.
Lista kroków dla procedury rekurencyjnej Fermat ( p  )
K01: x ← ceil ( sqr ( p ) ) obliczamy wartość początkową dla x
K02:     z ← x 2 - p z = y 2
K03:     y ← ceil ( sqr ( z ) ) sprawdzamy, czy z jest kwadratem liczby naturalnej
K04:     Jeśli z ≠ y 2,
    to idź do kroku K11
 
K05:     m ← x + y obliczamy czynniki
K06:     n ← x - y  
K07:     Jeśli n = 1,
    to idź do kroku K13
przerywamy przy n = 1, gdyż p jest pierwsze
K08:     Fermat ( m ) rozkładamy rekurencyjnie czynniki m i n
K09:     Fermat ( n )  
K10:     Zakończ  
K11:     x ← x + 1 następne x
K12:     Jeśli x + y < p,
    to idź do kroku K02
kontynuujemy pętlę
K13: Pisz p p jest pierwsze
K14: Zakończ  

Przykładowe programy

Uwaga:

Zanim uruchomisz program, przeczytaj wstęp do tego artykułu, w którym wyjaśniamy funkcje tych programów oraz sposób korzystania z nich.

Program w pierwszym wierszu czyta dowolną liczbę naturalną p  > 1 i w następnym wierszu wypisuje kolejne czynniki pierwsze tej liczby. Czynniki mogą nie być wypisywane w kolejności rosnącej. Zwróć uwagę, iż do poprawnego działania zmienna x musi być zadeklarowana jako 64 bitowa – w przeciwnym razie dla dużych liczb jej kwadrat wyjdzie poza zakres liczb 32-bitowych. W efekcie program może dokonywać rozkładu na czynniki pierwsze liczb 32 bitowych.
Pascal
// Metoda Fermata
// Data   : 27.03.2008
// (C)2020 mgr Jerzy Wałaszek
//----------------------------

program prg;

uses math;

procedure Fermat ( p : longword );

var x, y, z, m, n : qword;

begin
  x := ceil ( sqrt ( p ) );
  repeat
    z := x * x - p;
    y := floor ( sqrt ( z ) );
    if z = y * y then
    begin
      m := x + y;
      n := x - y;
      if n = 1 then break;
      Fermat ( m );
      Fermat ( n );
      exit;
    end;
    inc ( x );
  until x + y >= p;
  write ( p, ' ' );
end;

var p : longword;

begin
  readln ( p );
  while p mod 2 = 0 do
  begin
    p := p div 2;
    write ( 2, ' ' );
  end;
  if p > 1 then Fermat ( p );
  writeln;
end.
C++
// Metoda Fermata
// Data   : 27.03.2008
// (C)2020 mgr Jerzy Wałaszek
//----------------------------

#include <iostream>
#include <cmath>

using namespace std;

void Fermat ( unsigned int p )
{
  unsigned long long x, y, z, m, n;

  x = ( unsigned long long )ceil ( sqrt ( p ) );
  do
  {
    z = x * x - p;
    y = ( unsigned long long )floor ( sqrt ( z ) );
    if( z == y * y )
    {
      m = x + y;
      n = x - y;
      if( n == 1 ) break;
      Fermat ( m );
      Fermat ( n );
      return;
    }
    x++;
  } while( x + y < p );
  cout << p << " ";
}

int main( )
{
  unsigned int p;

  cin >> p;
  while( p % 2 == 0 )
  {
    p /= 2;
    cout << 2 << " ";
  }
  if( p > 1 ) Fermat ( p );
  cout << endl;
  return 0;
}
Basic
' Metoda Fermata
' Data   : 27.03.2008
' (C)2020 mgr Jerzy Wałaszek
'----------------------------

Sub Fermat ( Byval p As Uinteger )

Dim As Ulongint x, y, z, m, n

  x = Ceil ( Sqr ( p ) )
  Do
    z = x * x - p
    y = Floor ( Sqr ( z ) )
    If z = y * y Then
      m = x + y
      n = x - y
      If n = 1 Then Exit Do
      Fermat ( m )
      Fermat ( n )
      Exit Sub
    End If
    x += 1
  Loop Until x + y >= p
  Print p;" ";
End Sub

Function Ceil ( Byval x As Double ) As Ulongint
   Dim result As Ulongint
   result = Culngint ( x )
   If result < x Then result += 1
   Ceil = result
End Function

Function Floor ( Byval x As Double ) As Ulongint
   Dim result As Ulongint
   result = Culngint ( x )
   If result > x Then result -= 1
   Floor = result
End Function

Dim p As Uinteger

Input p
while p mod 2 = 0
  p = p shr 1
  print 2;" ";
wend
if p > 1 then Fermat ( p )
Print
End
Wynik:
855855
11 7 13 3 3 5 19
Na początek:  podrozdziału   strony 

Rozwiązanie 2

Podstawową wadą pierwszego rozwiązania jest konieczność wyznaczania wartości pierwiastka kwadratowego. Niestety, jest to operacja dosyć czasochłonna. Zastanówmy się zatem, czy algorytmu Fermata nie można zapisać w inny sposób, tak aby nie było konieczności wyznaczania pierwiastków kwadratowych w pętli poszukującej dzielników. Dokonajmy najpierw kilku prostych spostrzeżeń.

Jeśli mamy daną wartość kwadratu liczby naturalnej, np. x 2, to kwadrat następnej liczby x + 1 można wyznaczyć następująco:

( x  + 1 ) 2 = x 2 + 2x  + 1 = x 2 + dx, gdzie dx  = 2x  + 1

Ponieważ x  wzrosło o 1, to nowy przyrost dx'  wyniesie:

dx '  = 2 ( x  + 1 ) + 1 = 2x  + 2 + 1 = ( 2x  + 1 ) + 2 = dx  + 2

Wynika stąd, iż mając wartość początkową kwadratu x 2 oraz dx, kolejne kwadraty obliczamy w pętli wg reguły:

x ' 2 = x 2 + dx,   x  = ( dx  - 1 ) / 2,   dx ' = dx  + 2

Poniższy program demonstruje tę zasadę wyznaczania kwadratów kolejnych liczb naturalnych od 0 do 15.

kx  – kwadrat x, początkowo 0
dx  – przyrost kwadratu, początkowo dx  = 1, gdyż x  = 0
x  – kolejna liczba od 0 do 15. Liczbę tę wyznaczamy bezpośrednio z przyrostu dx.

Przykładowe programy

Uwaga:

Zanim uruchomisz program, przeczytaj wstęp do tego artykułu, w którym wyjaśniamy funkcje tych programów oraz sposób korzystania z nich.

Pascal
// Wyznaczanie kwadratów
// kolejnych liczb naturalnych
// Data   : 2.04.2008
// (C)2020 mgr Jerzy Wałaszek
//----------------------------

program prg;

var kx, dx, x : integer; 

begin
  kx := 0; dx := 1;
  repeat
    x := ( dx - 1 ) shr 1;
    writeln ( x:5, kx:5 );
    inc ( kx, dx ); inc ( dx, 2 );
  until x = 15;
  writeln;
end.
   C++
// Wyznaczanie kwadratów
// kolejnych liczb naturalnych
// Data   : 2.04.2008
// (C)2020 mgr Jerzy Wałaszek
//----------------------------

#include <iostream>
#include <iomanip>

using namespace std;

int main( )
{
  int kx, dx, x; 

  kx = 0; dx = 1;
  do
  {
    x = ( dx - 1 ) >> 1;
    cout << setw ( 5 ) << x 
         << setw ( 5 ) << kx
         << endl;
    kx += dx; dx += 2;
  } while( x < 15 );
  cout << endl;
  return 0;
}
   Basic
' Wyznaczanie kwadratów
' kolejnych liczb naturalnych
' Data   : 2.04.2008
' (C)2020 mgr Jerzy Wałaszek
'----------------------------

Dim As Integer kx, dx, x

kx = 0: dx = 1
Do
  x = ( dx - 1 ) Shr 1
  Print Using "#### ####";x;kx
  kx += dx: dx += 2
Loop Until x = 15
Print
End
Wynik:
  0    0
  1    1
  2    4
  3    9
  4   16
  5   25
  6   36
  7   49
  8   64
  9   81
 10  100
 11  121
 12  144
 13  169
 14  196
 15  225

Zastosujmy następującą strategię. Mamy daną liczbę naturalną p, p  > 1 i p  jest nieparzyste. Obliczamy:

x  = ceil ( sqr ( p ) ), y  = 0
e
  = x 2 - y 2 - p

Liczba e  jest wartością błędu pomiędzy x 2 - y 2 a liczbą p. Wyznaczamy przyrosty dla x 2 oraz dla y 2:

dx  = 2x  + 1
dy  = 2y  + 1 = 1, gdyż początkowo y  = 0

Teraz w pętli badamy błąd e. Jeśli jest równy 0, to

p  = x 2 - y 2
x  = ( dx  - 1 ) / 2
y  = ( dy  - 1 ) / 2
m  = x  + y = ( dx  - 1 ) / 2 + ( dy  - 1 ) / 2 = ( dx  + dy  - 2 ) / 2 = ( dx  + dy  ) / 2 - 1
n  = x  - y  = ( dx  - 1 ) / 2 - ( dy  - 1 ) / 2 = ( dx  - dy  ) / 2

Jeśli n  jest różne od 1, to m  i n  rozkładamy dalej na czynniki tym samym algorytmem. W przeciwnym razie liczba p  jest pierwsza, zwracamy ją i kończymy.

Jeśli e  jest różne od zera, to nie znaleźliśmy jeszcze x  i y  spełniających równanie Fermata. Badamy znak e.

Jeśli e  > 0, to przeważa x 2, zatem zwiększamy y 2 i odejmujemy od e  przyrost dy. Po tej operacji dy  jest zwiększane o 2, aby w kolejnym obiegu otrzymać kwadrat następnego y – a właściwie jego przyrost w stosunku do poprzedniego kwadratu. Zwiększanie y  kontynuujemy do momentu, aż e  ≤ 0, czyli aż osiągniemy równowagę lub przeważy y 2.

Jeśli e  < 0, to przeważa y 2, zatem zwiększamy x 2 i dodajemy do e  przyrost dx, który następnie zwiększamy o 2. Operację kontynuujemy do momentu, aż e  ≥ 0.

Wracamy na początek pętli, aż do uzyskania e  = 0. W tym miejscu algorytm można zoptymalizować, sprawdzając, czy x  + y  ≥ p, czyli ( dx  + dy  ) / 2 > p. Jeśli tak, to liczba p  jest pierwsza i nie znajdziemy rozkładu na inne czynniki poza p  i 1. Zatem przerywamy pętlę zwracając p.

Zwróć uwagę, iż w tej wersji algorytmu Fermata nie wykonujemy w pętli operacji pierwiastkowania, a jedynie proste dodawania. Dzięki temu algorytm staje się dużo szybszy od algorytmu podanego w rozwiązaniu 1.

Algorytm rozkładu liczby naturalnej na czynniki pierwsze metodą Fermata

Wejście:

p  –   liczba rozkładana na czynniki pierwsze, p  ∈ N, p  jest nieparzyste.

Wyjście:

Czynniki pierwsze liczby p.

Zmienne pomocnicze:

e  –  wartość błędu. e  ∈ C.
m, n  – czynniki p, m, n  ∈ N.
dx, dy  – przyrosty kwadratów x  i y. dx, dy  ∈ N.

Lista kroków dla procedury rekurencyjnej Fermat ( p  )

K01: m  ← ceil( sqr ( p ) ) wyznaczamy wartość błędu e oraz przyrosty dx i dy
K02: e  ← m 2 - p e = x 2 - p, ponieważ początkowo y = 0
K03: dx  ← 2m  + 1 dx – przyrost x 2
K04: dy  ← 1 dy – przyrost y 2
K05: Dopóki e  ≠ 0,
wykonuj kroki K06...K16
w pętli staramy się zrównać x 2 - y 2  z p - wtedy e = 0
K06:     Dopóki e  > 0,
    wykonuj kroki K07...K08
przeważa x 2, zwiększamy y 2
K07:         e  ←  e  - dy modyfikujemy błąd o przyrost y 2
K08         dy  ←  dy  + 2 przyrost y 2 dla zwiększonego o 1 y
K09:     Dopóki e  < 0,
    wykonuj
kroki K10...K11
przeważa y 2, zwiększamy x 2
K10:         e  ←  e  + dx modyfikujemy błąd o przyrost x 2
K11:         dx  ←  dx  + 2 przyrost x 2 dla zwiększonego x
K12:     Jeśli ( dx  + dy  ) / 2 ≤ p,
    to następny obieg pętli K05
sprawdzamy drugi warunek zakończenia pętli
K13:     dx  ← 2 jeśli jest spełniony, to p jest liczbą pierwszą
K14:     dy  ← 0 dx i dy ustawiamy tak, aby otrzymać n = 1
K15:     Idź do kroku K16 przerywamy pętlę K05
K16: m  ← ( dx  + dy  ) / 2 - 1 czynnik większy
K17: n  ← ( dx  - dy  ) / 2 czynnik mniejszy
K18: Jeśli n  = 1,
to idź do kroku K21
sprawdzamy, czy p jest pierwsze
K19: Fermat ( m  );   Fermat ( n  ) jeśli nie, to czynniki m i n rozkładamy dalej
K20: Zakończ  
K21: Pisz p p jest pierwsze. Wyprowadzamy je i kończymy
K22: Zakończ  

Przykładowe programy

Uwaga:

Zanim uruchomisz program, przeczytaj wstęp do tego artykułu, w którym wyjaśniamy funkcje tych programów oraz sposób korzystania z nich.

Program w pierwszym wierszu czyta liczbę p  i w następnym wierszu wypisuje kolejne czynniki pierwsze tej liczby.  Liczba p  nie musi być nieparzysta. Przed przekazaniem jej do procedury Fermat program usuwa z p  wszystkie czynniki równe 2.
Pascal
// Metoda Fermata
// Data   : 2.04.2008
// (C)2020 mgr Jerzy Wałaszek
//----------------------------

uses math;

procedure Fermat ( p : int64 );

var e, dx, dy, m, n : int64;

begin
  m  := ceil ( sqrt ( p ) );
  dx := ( m shl 1 ) + 1;
  e  := m * m - p;
  dy := 1;
  while e <> 0 do
  begin
    while e > 0 do
    begin
      dec ( e, dy ); inc ( dy, 2 );
    end;
    while e < 0 do
    begin
      inc ( e, dx ); inc ( dx, 2 );
    end;
    if( dx + dy ) shr 1 > p then
    begin
      dx := 2; dy := 0; break;
    end;
  end;
  m := ( ( dx + dy ) shr 1 ) - 1;
  n := ( dx - dy ) shr 1;
  if n > 1 then
  begin
    Fermat ( m ); Fermat ( n );
  end
  else write ( p, ' ' );
end;

var p : int64;

begin
  readln ( p );
  while p mod 2 = 0 do
  begin
    write ( 2, ' ' );
    p := p shr 1;
  end;
  if p > 1 then Fermat ( p );
  writeln;
end.
   C++
// Metoda Fermata
// Data   : 2.04.2008
// (C)2020 mgr Jerzy Wałaszek
//----------------------------

#include <cstdlib>
#include <iostream>
#include <cmath>

using namespace std;

void Fermat ( long long p )
{
  long long e, dx, dy, m, n;
  m  = ( long long )sqrt ( p );
  dx = ( m << 1 ) + 1;
  e  = m * m - p;
  dy = 1;
  while( e != 0 )
  {
    while( e > 0 )
    {
      e -= dy; dy += 2;
    }
    while( e < 0 )
    {
      e += dx; dx += 2;
    }
    if( ( ( dx + dy ) >> 1 ) > p )
    {
      dx = 2; dy = 0; break;
    }
  }
  m = ( ( dx + dy ) >> 1 ) - 1;
  n = ( dx - dy ) >> 1;
  if( n != 1 )
  {
    Fermat ( m ); Fermat ( n );
  }
  else cout << p << " ";
}

int main( )
{
  long long p;
  cin >> p;
  while( p % 2 == 0 )
  {
    cout << 2 << " ";
    p >>= 1;
 }
 if( p > 1 ) Fermat ( p );
 cout << endl;
 return 0;
}
   Basic
' Metoda Fermata
' Data   : 2.04.2008
' (C)2020 mgr Jerzy Wałaszek
'----------------------------

Sub Fermat ( Byval p As Longint )

  Dim As Longint e, dx, dy, m, n

  m  = Clngint ( Sqr ( p ) )
  dx = ( m Shl 1 ) + 1
  e  = m * m - p
  dy = 1
  While e
    While e > 0
      e -= dy: dy += 2
    Wend
    While e < 0
      e += dx: dx += 2
    Wend
    if( dx + dy ) Shr 1 > p Then
      dx = 2: dy = 0: Exit While
    End If
  Wend
  m = ( ( dx + dy ) Shr 1 ) - 1
  n = ( dx - dy ) Shr 1
  If n > 1 Then
    Fermat ( m ): Fermat ( n )
  Else
    Print p;" ";
  End If
End Sub

Dim p As Longint
  
Input p
While p Mod 2 = 0
  Print 2;" ";
  p = p Shr 1
Wend
If p > 1 Then Fermat ( p )
Print
End
Wynik:
254821743888
2 2 2 2 230816797 23 3
Rozkład na czynniki pierwsze metodą Fermata
(C)2020 mgr Jerzy Wałaszek

p =


...

Na początek:  podrozdziału   strony 

Rozwiązanie 3

Większość liczb złożonych posiada czynniki pierwsze o małych wartościach. Algorytm Fermata jest szczególnie wydajny dla czynników leżących w pobliżu pierwiastka rozkładanej liczby. Natomiast czynniki małe są znajdowane wolno. Proponowane tutaj ulepszenie polega na połączeniu algorytmu próbnych dzieleń z algorytmem Fermata. W tablicy przechowujemy kolejne liczby pierwsze od 2 do 1009 – jest ich 169. Przed przekazaniem liczby p  do procedury Fermat, z liczby p  usuwamy wszystkie czynniki pierwsze przechowywane w tablicy. Jeśli liczba posiada takie czynniki, to po usunięciu ich staje się dużo mniejsza – zatem algorytm Fermata szybciej znajdzie pozostałe, duże czynniki pierwsze. Czas wykonania 169 próbnych dzieleń jest bardzo mały dla współczesnych procesorów, zatem warto zastosować to ulepszenie.


Przykładowe programy

Uwaga:

Zanim uruchomisz program, przeczytaj wstęp do tego artykułu, w którym wyjaśniamy funkcje tych programów oraz sposób korzystania z nich.

Pascal
// Metoda Fermata
// Data   : 2.04.2008
// (C)2020 mgr Jerzy Wałaszek
//----------------------------

uses math;

procedure Fermat ( p : int64 );

var e, dx, dy, m, n : int64;

begin
  m  := ceil ( sqrt ( p ) );
  dx := ( m shl 1 ) + 1;
  e  := m * m - p;
  dy := 1;
  while e <> 0 do
  begin
    while e > 0 do
    begin
      dec ( e, dy ); inc ( dy, 2 );
    end;
    while e < 0 do
    begin
      inc ( e, dx ); inc ( dx, 2 );
    end;
    if( dx + dy ) shr 1 > p then
    begin
      dx := 2; dy := 0; break;
    end;
  end;
  m := ( ( dx + dy ) shr 1 ) - 1;
  n := ( dx - dy ) shr 1;
  if n > 1 then
  begin
    Fermat ( m ); Fermat ( n );
  end
  else write ( p, ' ' );
end;

const lp : array [ 0..168 ] of integer = ( 
  2,  3,  5,  7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 
 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 
167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 
271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 
389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 
503, 509, 521, 523, 541, 547, 557, 563, 569, 571, 577, 587, 593, 599, 601, 607, 613, 617, 619, 
631, 641, 643, 647, 653, 659, 661, 673, 677, 683, 691, 701, 709, 719, 727, 733, 739, 743, 751, 
757, 761, 769, 773, 787, 797, 809, 811, 821, 823, 827, 829, 839, 853, 857, 859, 863, 877, 881, 
883, 887, 907, 911, 919, 929, 937, 941, 947, 953, 967, 971, 977, 983, 991, 997, 1009 );

var
  p : int64;
  i : integer;

begin
  readln ( p );
  for i := 0 to 168 do
  begin
    if p >= lp [ i ] then
      while p mod lp [ i ] = 0 do
      begin
        write ( lp [ i ], ' ' );
        p := p div lp [ i ];
      end
    else break;
  end;
  if p > 1 then Fermat ( p );
  writeln;
end.
C++
// Metoda Fermata
// Data   : 2.04.2008
// (C)2020 mgr Jerzy Wałaszek
//----------------------------

#include <cstdlib>
#include <iostream>
#include <cmath>

using namespace std;

void Fermat ( long long p )
{
  long long e, dx, dy, m, n;
  m  = ( long long )sqrt ( p );
  dx = ( m << 1 ) + 1;
  e  = m * m - p;
  dy = 1;
  while( e != 0 )
  {
    while( e > 0 )
    {
      e -= dy; dy += 2;
    }
    while( e < 0 )
    {
      e += dx; dx += 2;
    }
    if( ( ( dx + dy ) >> 1 ) > p )
    {
      dx = 2; dy = 0; break;
    }
  }
  m = ( ( dx + dy ) >> 1 ) - 1;
  n = ( dx - dy ) >> 1;
  if( n != 1 )
  {
    Fermat ( m ); Fermat ( n );
  }
  else cout << p << " ";
}

int main( )
{
  const int lp [ ] = {
  2,  3,  5,  7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 
 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 
167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 
271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 
389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 
503, 509, 521, 523, 541, 547, 557, 563, 569, 571, 577, 587, 593, 599, 601, 607, 613, 617, 619, 
631, 641, 643, 647, 653, 659, 661, 673, 677, 683, 691, 701, 709, 719, 727, 733, 739, 743, 751, 
757, 761, 769, 773, 787, 797, 809, 811, 821, 823, 827, 829, 839, 853, 857, 859, 863, 877, 881, 
883, 887, 907, 911, 919, 929, 937, 941, 947, 953, 967, 971, 977, 983, 991, 997, 1009};

  long long p;
  int i;

  cin >> p;
  for( i = 0; i < 169; i++ )
  {
    if( p >= lp [ i ] )
      while( p % lp [ i ] == 0 )
      {
        cout << lp [ i ] << " ";
        p /= lp [ i ];
      }
    else break;
  }
  if( p > 1 ) Fermat ( p );
  cout << endl;
  return 0;
}
Basic
' Metoda Fermata
' Data   : 2.04.2008
' (C)2020 mgr Jerzy Wałaszek
'----------------------------

Sub Fermat ( Byval p As Longint )

  Dim As Longint e, dx, dy, m, n

  m  = Clngint ( Sqr ( p ) )
  dx = ( m Shl 1 ) + 1
  e  = m * m - p
  dy = 1
  While e
    While e > 0
      e -= dy: dy += 2
    Wend
    While e < 0
      e += dx: dx += 2
    Wend
    if( dx + dy ) Shr 1 > p Then
      dx = 2: dy = 0: Exit While
    End If
  Wend
  m = ( ( dx + dy ) Shr 1 ) - 1
  n = ( dx - dy ) Shr 1
  If n > 1 Then
    Fermat ( m ): Fermat ( n )
  Else
    Print p;" ";
  End If
End Sub

Dim lp ( 168 ) As Integer => {_
  2,  3,  5,  7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, _
 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, _
167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, _
271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, _
389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, _
503, 509, 521, 523, 541, 547, 557, 563, 569, 571, 577, 587, 593, 599, 601, 607, 613, 617, 619, _
631, 641, 643, 647, 653, 659, 661, 673, 677, 683, 691, 701, 709, 719, 727, 733, 739, 743, 751, _
757, 761, 769, 773, 787, 797, 809, 811, 821, 823, 827, 829, 839, 853, 857, 859, 863, 877, 881, _
883, 887, 907, 911, 919, 929, 937, 941, 947, 953, 967, 971, 977, 983, 991, 997, 1009}

Dim p As Longint, i As Integer

Input p
For i = 0 To 168
  If p >= lp ( i ) Then
    While p Mod lp ( i ) = 0
      Print lp ( i );" ";
      p \= lp ( i )
    Wend
  Else
    Exit For
  End If
Next
If p > 1 Then Fermat ( p )
Print
End
Wynik:
1234567891011
3 7 13 67 107 630803

1111111111111111
11 17 73 101 137 5882353

222222222222222222
2 3 3 7 11 13 19 37 333667 52579
Na początek:  podrozdziału   strony 

Zespół Przedmiotowy
Chemii-Fizyki-Informatyki

w I Liceum Ogólnokształcącym
im. Kazimierza Brodzińskiego
w Tarnowie
ul. Piłsudskiego 4
©2020 mgr Jerzy Wałaszek

Materiały tylko do użytku dydaktycznego. Ich kopiowanie i powielanie jest dozwolone
pod warunkiem podania źródła oraz niepobierania za to pieniędzy.

Pytania proszę przesyłać na adres email: i-lo@eduinf.waw.pl

Serwis wykorzystuje pliki cookies. Jeśli nie chcesz ich otrzymywać, zablokuj je w swojej przeglądarce.
Informacje dodatkowe.