Czynniki pierwsze – metoda Fermata


Tematy pokrewne   Podrozdziały
Przedziały liczbowe i liczby
Liczby parzyste i nieparzyste
Liczby podzielne lub niepodzielne przez zadane podzielniki
Ciągi arytmetyczne
NWD – algorytm Euklidesa
Liczby względnie pierwsze
Najmniejsza wspólna wielokrotność
Odwrotność modulo – rozszerzony algorytm Euklidesa
Liczby pierwsze – generacja przez sprawdzanie podzielności
Liczby pierwsze – generacja sitem Eratostenesa
Liczby pierwsze – generacja sitem liniowym
Liczby pierwsze – generacja sitem Atkina-Bernsteina
Czynniki pierwsze – metoda próbnych dzieleń
Czynniki pierwsze – metoda Fermata
Pierwszość liczby naturalnej – algorytmy naiwne
Pierwszość liczby naturalnej – Chiński Test Pierwszości
Pierwszość liczby naturalnej – Małe Twierdzenie Fermata
Pierwszość liczby naturalnej – test Millera-Rabina
Liniowe generatory liczb pseudolosowych
Generator pseudolosowy Park-Miller
Generator pseudolosowy Mersenne Twister
Wbudowane generatory liczb pseudolosowych
Generowanie liczb pseudolosowych
Liczby Fibonacciego
System liczbowy Fibonacciego
Całkowity pierwiastek kwadratowy
  Rozwiązanie 1
Rozwiązanie 2
Rozwiązanie 3

 

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 = x2 - y2,

 

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 = x2 - y2 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:

 

y2 = x2 - 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 + yp

 

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.

Elementy 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 ← ⌈√p⌉ ; obliczamy wartość początkową dla x
K02:     z ← x2 - p ; z = y2
K03:     y ← ⌊√z⌋ ; sprawdzamy, czy z jest kwadratem liczby naturalnej
K04:     Jeśli z ≠ y2, to idź do K11  
K05:     m ← x + y ; obliczamy czynniki
K06:     n ← x - y  
K07:     Jeśli n = 1, to idź do 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 K02 ; kontynuujemy pętlę
K13: Pisz p ; p jest pierwsze
K14: Zakończ  

 

Program

Ważne:

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.

 

Lazarus
// Metoda Fermata
// Data   : 27.03.2008
// (C)2012 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.
Code::Blocks
// Metoda Fermata
// Data   : 27.03.2008
// (C)2012 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;
}
Free Basic
' Metoda Fermata
' Data   : 27.03.2008
' (C)2012 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

 

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. x2, to kwadrat następnej liczby x + 1 można wyznaczyć następująco:

 

(x + 1)2 = x2 + 2x + 1 = x2 + 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 x2 oraz dx, kolejne kwadraty obliczamy w pętli wg reguły:

 

x'2 = x2 + dxx = (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.

 

Program

Ważne:

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.

 
Lazarus Code::Blocks Free Basic
// Wyznaczanie kwadratów
// kolejnych liczb naturalnych
// Data   : 2.04.2008
// (C)2012 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.
// Wyznaczanie kwadratów
// kolejnych liczb naturalnych
// Data   : 2.04.2008
// (C)2012 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;
}
' Wyznaczanie kwadratów
' kolejnych liczb naturalnych
' Data   : 2.04.2008
' (C)2012 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 = ⌈√p⌉,  y = 0

e = x2 - y2 - p

 

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

 

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 = x2 - y2
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 x2, zatem zwiększamy y2 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 y2.

Jeśli e < 0, to przeważa y2, zatem zwiększamy x2 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 + yp, 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.

Elementy 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 ← ⌈√p ; wyznaczamy wartość błędu e oraz przyrosty dx i dy
K02: em2 - p ; e = x2 - p, ponieważ początkowo y = 0
K03: dx ← 2m + 1 ; dx – przyrost x2
K04: dy ← 1 ; dy – przyrost y2
K05: Dopóki e ≠ 0, wykonuj kroki K06...K16 ; w pętli staramy się zrównać x2 - y2  z p - wtedy e = 0
K06:     Dopóki e > 0, wykonuj kroki K07...K08 ; przeważa x2, zwiększamy y2
K07:         ee - dy ; modyfikujemy błąd o przyrost y2
K08         dydy + 2 ; przyrost y2 dla zwiększonego o 1 y
K09:     Dopóki e < 0, wykonuj kroki K10...K11 ; przeważa y2, zwiększamy x2
K10:         ee + dx ; modyfikujemy błąd o przyrost x2
K11:         dxdx + 2 ; przyrost x2 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 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 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  

 

Program

Ważne:

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.

 

Lazarus Code::Blocks Free Basic
// Metoda Fermata
// Data   : 2.04.2008
// (C)2012 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.
// Metoda Fermata
// Data   : 2.04.2008
// (C)2012 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;
}
' Metoda Fermata
' Data   : 2.04.2008
' (C)2012 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)2012 mgr Jerzy Wałaszek

p =


...

 

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.

 

Program

Ważne:

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.

 
Lazarus
// Metoda Fermata
// Data   : 2.04.2008
// (C)2012 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.
Code::Blocks
// Metoda Fermata
// Data   : 2.04.2008
// (C)2012 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;
}
Free Basic
' Metoda Fermata
' Data   : 2.04.2008
' (C)2012 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

 

Rozkład na czynniki pierwsze metodą Fermata
(C)2012 mgr Jerzy Wałaszek

p =


...

 



List do administratora Serwisu Edukacyjnego Nauczycieli I LO

Twój email: (jeśli chcesz otrzymać odpowiedź)
Temat:
Uwaga: ← tutaj wpisz wyraz  ilo , inaczej list zostanie zignorowany

Poniżej wpisz swoje uwagi lub pytania dotyczące tego rozdziału (max. 2048 znaków).

Liczba znaków do wykorzystania: 2048

 

W związku z dużą liczbą listów do naszego serwisu edukacyjnego nie będziemy udzielać odpowiedzi na prośby rozwiązywania zadań, pisania programów zaliczeniowych, przesyłania materiałów czy też tłumaczenia zagadnień szeroko opisywanych w podręcznikach.



   I Liceum Ogólnokształcące   
im. Kazimierza Brodzińskiego
w Tarnowie

©2017 mgr Jerzy Wałaszek

Dokument ten rozpowszechniany jest zgodnie z zasadami licencji
GNU Free Documentation License.