1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
|
use crate::lab_trait::Lab;
use eframe::egui;
use rug::{Complete, Integer};
enum State {
Clean,
Done,
Error,
}
pub struct Window {
str_num: String,
factors: Vec<Integer>,
state: State,
}
impl Default for Window {
fn default() -> Self {
Self {
str_num: String::from("21894583143407671"),
factors: Vec::new(),
state: State::Clean,
}
}
}
impl Lab for Window {
fn get_name(&self) -> &str { "Задача №3" }
fn update(&mut self, ui: &mut egui::Ui) {
ui.horizontal(|ui| {
ui.label("Число: ");
let field = ui.add(egui::TextEdit::singleline(&mut self.str_num));
if field.changed() {
self.state = State::Clean;
self.factors.clear();
}
});
if ui.button("Разложить на множители").clicked() {
self.factors.clear();
match Integer::parse(&self.str_num) {
Ok(number) => {
self.factors.append(&mut factorize(&number.complete()));
self.state = State::Done;
},
Err(_) => self.state = State::Error,
};
}
if let State::Done = self.state {
if self.factors.len() == 1 {
ui.label(format!("Число является простым"));
}
else {
ui.label(format!("Множители: {:?}", self.factors));
}
}
if let State::Error = self.state {
ui.label("В числе имеются недопустимые символы");
}
}
}
fn factorize(n: &Integer) -> Vec<Integer> {
let mut factors = Vec::new();
let mut front = vec![n.clone()];
while !front.is_empty() {
let num = front.pop().unwrap();
match lehman(&num) {
Some(factor) => {
let other = num.div_exact_ref(&factor).complete();
front.push(factor);
front.push(other);
},
None => factors.push(num)
};
}
return factors;
}
fn lehman(n: &Integer) -> Option<Integer> {
let one = &Integer::from(1u32);
let mut a = Integer::from(2u32);
let root3 = n.root_ref(3).complete();
while a <= root3 {
let (_, r) = n.div_rem_ref(&a).complete();
if r == 0 {
return Some(a);
}
a += one;
}
let root6 = n.root_ref(6).complete();
let mut k = Integer::from(1u32);
while k <= root3 {
let mut d = Integer::ZERO;
let sqrtk4 = k.sqrt_ref().complete() * 4;
let (r6sk4, _) = root6.div_rem_ref(&sqrtk4).complete();
while d <= (&r6sk4 + one).complete() {
let kn4: Integer = k.clone() * n.clone() * 4;
let sqrt_kn4 = kn4.sqrt_ref().complete();
let number = (sqrt_kn4.clone() + d.clone()).square() - kn4.clone();
if number.is_perfect_square() {
let big_a = sqrt_kn4 + d.clone();
let big_b = (big_a.square_ref() - kn4).sqrt();
let gcd1 = (big_a.clone() + big_b.clone()).gcd_ref(n).complete();
let gcd2 = (big_a.clone() - big_b.clone()).gcd_ref(n).complete();
if &gcd1 > one && &gcd1 < n {
return Some(gcd1);
}
else if &gcd2 > one && &gcd2 < n {
return Some(gcd2);
}
}
d += one;
}
k += one;
}
return None;
}
|
