|
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 ← 2m + 1 ; dx – przyrost x2 K04: dy ← 1 ; dy – przyrost y2 K05: Dopóki e ≠ 0: ; w pętli staramy się zrównać x2 - y2 z p - wtedy e = 0 wykonuj kroki K06…K16 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 zakończenia pętli to następny obieg pętli K05 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 m i n rozkładamy dalej Fermat(n) 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.
