1 files changed, 128 insertions, 0 deletions
diff --git a/labs/src/lab3.rs b/labs/src/lab3.rs
new file mode 100644
index 0000000..7f8edf5
--- /dev/null
+++ b/labs/src/lab3.rs
@@ -0,0 +1,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;
+}
+