|
Serwis Edukacyjny w I-LO w Tarnowie 
Materiały dla uczniów liceum |
Wyjście Spis treści Wstecz Dalej
Autor artykułu: mgr Jerzy Wałaszek |
©2024 mgr Jerzy Wałaszek
|
|
Serwis Edukacyjny w I-LO w Tarnowie
Materiały dla uczniów liceum |
Wyjście Spis treści Wstecz Dalej
Autor artykułu: mgr Jerzy Wałaszek |
©2024 mgr Jerzy Wałaszek
|
ProblemZnaleźć 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 o wartości 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. |
Algorytm wykorzystuje bezpośrednio własność
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
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.
K01: x ← ceil(sqr(p)) ; obliczamy wartość początkową dla x K02: z ← x2-p ; z = y2 K03: y ← ceil(sqr(z)) ; sprawdzamy, czy z jest kwadratem liczby naturalnej K04: Jeśli z ≠ y2, to idź do kroku K11 K05: m ← x+y ; obliczamy czynniki K06: n ← x-y K07: Jeśli n = 1, ; przerywamy przy n = 1, gdyż p jest pierwsze to idź do kroku K13 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, ; kontynuujemy pętlę to idź do kroku K02 K13: Pisz p ; p jest pierwsze K14: Zakończ
|
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. |
// 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 |
Python (dodatek)# Metoda Fermata
# Data : 12.02.2024
# (C)2024 mgr Jerzy Wałaszek
# --------------------------
import math
def fermat(p):
x = math.ceil(math.sqrt(p))
while 1:
z = x*x-p
y = math.floor(math.sqrt(z))
if z == y*y:
m = x+y
n = x-y
if n == 1: break
fermat(m)
fermat(n)
return
x += 1
if x+y >= p: break
print(p, end=" ")
return
p = int(input())
while not (p % 2):
p >>= 1
print(2, end=" ")
if p > 1: fermat(p)
print()
|
| Wynik: |
855855 11 7 13 3 3 5 19 |
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+dx, x = (dx-1)/2 dx' = dx+2
Poniższy program demonstruje tę zasadę wyznaczania kwadratów kolejnych liczb naturalnych od 0 do 15.
|
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. |
// 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 |
Python (dodatek)# Wyznaczanie kwadratów
# kolejnych liczb naturalnych
# Data : 12.02.2024
# (C)2024 mgr Jerzy Wałaszek
#---------------------------
kx, dx = 0, 1
while 1:
x = (dx-1) >> 1
print("%4d %4d" % (x, kx))
kx += dx
dx += 2
if x == 15: break
print()
|
| 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 = 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+y ≥ p, czyli
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.
K01: m ← ceil(sqr(p)) ; wyznaczamy wartość błędu e ' oraz przyrosty dx i dy K02: e ← m2-p ; e = x2-p, ponieważ początkowo y = 0 K03: dx ← 2×m+1 ; dx – przyrost x2 K04: dy ← 1 ; dy – przyrost y2 K05: Dopóki e ≠ 0: ; w pętli staramy się zrównać wykonuj kroki K06…K16 ; x2-y2 z p-wtedy e = 0 K06: Dopóki e > 0: ; przeważa x2, zwiększamy y2 wykonuj kroki K07…K08 K07: e ← e-dy ; modyfikujemy błąd o przyrost y2 K08: dy ← dy+2 ; przyrost y2 dla zwiększonego o 1 y K09: Dopóki e < 0: ; przeważa y2, zwiększamy x2 wykonuj kroki K10…K11 K10: e ← e+dx ; modyfikujemy błąd o przyrost x2 K11: dx ← dx+2 ; przyrost x2 dla zwiększonego x K12: Jeśli (dx+dy)/2 ≤ p, ; sprawdzamy drugi warunek to następny obieg pętli K05 ; 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, ; sprawdzamy, czy p jest pierwsze to idź do kroku K21 K19: Fermat(m) ; jeśli nie, to czynniki Fermat(n) ; m i n rozkładamy dalej K20: Zakończ K21: Pisz p ; p jest pierwsze. ; Wyprowadzamy je i kończymy K22: Zakończ
|
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 |
Python (dodatek)# Metoda Fermata
# Data : 12.02.2024
# (C)2024 mgr Jerzy Wałaszek
# --------------------------
import math
def fermat(p):
m = int(math.sqrt(p))
dx = (m << 1)+1
e = m*m-p
dy = 1
while e:
while e > 0:
e -= dy
dy += 2
while e < 0:
e += dx
dx += 2
if ((dx+dy) >> 1) > p:
dx, dy = 2, 0
break
m = ((dx+dy) >> 1)-1
n = (dx-dy) >> 1
if n != 1:
fermat(m)
fermat(n)
else:
print(p, end=" ")
return
p = int(input())
while not (p % 2):
print(2, end=" ")
p >>= 1
if p > 1:
fermat(p)
print()
|
| Wynik: |
| 254821743888 2 2 2 2 230816797 23 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.
|
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 |
Python (dodatek)# Metoda Fermata
# Data : 12.02.2024
# (C)2024 mgr Jerzy Wałaszek
# --------------------------
import math
def fermat(p):
m = int(math.sqrt(p))
dx = (m << 1)+1
e = m*m-p
dy = 1
while e:
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:
print(p, end=" ")
return
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]
p = int(input())
for i in range(169):
if p >= lp[i]:
while not (p % lp[i]):
print(lp[i], end=" ")
p //= lp[i]
else:
break
if p > 1:
fermat(p)
print()
|
| 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 |
 |
Zespół Przedmiotowy Chemii-Fizyki-Informatyki w I Liceum Ogólnokształcącym im. Kazimierza Brodzińskiego w Tarnowie ul. Piłsudskiego 4 ©2024 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:
Serwis wykorzystuje pliki cookies. Jeśli nie chcesz ich otrzymywać, zablokuj je w swojej przeglądarce.
Informacje dodatkowe.
