Добавлена реализация второй лабораторной

3 files changed, 112 insertions, 0 deletions

diff --git a/Cargo.lock b/Cargo.lock
index 6c786f2..79be396 100644
--- a/Cargo.lock
+++ b/Cargo.lock
@@ -78,6 +78,12 @@ source = "registry+https://github.com/rust-lang/crates.io-index"
 checksum = "d468802bab17cbc0cc575e9b053f41e72aa36bfa6b7f55e3529ffa43161b97fa"
 
 [[package]]
+name = "az"
+version = "1.2.1"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "7b7e4c2464d97fe331d41de9d5db0def0a96f4d823b8b32a2efd503578988973"
+
+[[package]]
 name = "bitflags"
 version = "1.3.2"
 source = "registry+https://github.com/rust-lang/crates.io-index"
@@ -692,6 +698,16 @@ dependencies = [
 ]
 
 [[package]]
+name = "gmp-mpfr-sys"
+version = "1.4.10"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "ea3f42dadb6c75f122e9aa87e757ef11d4282f664c9f2e6476a9c2c8970f9d19"
+dependencies = [
+ "libc",
+ "winapi",
+]
+
+[[package]]
 name = "ident_case"
 version = "1.0.1"
 source = "registry+https://github.com/rust-lang/crates.io-index"
@@ -759,6 +775,7 @@ name = "lab1"
 version = "0.1.0"
 dependencies = [
  "eframe",
+ "rug",
 ]
 
 [[package]]
@@ -1182,6 +1199,17 @@ dependencies = [
 ]
 
 [[package]]
+name = "rug"
+version = "1.17.0"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "203180f444c95eac53586ed04793ecf6454c5d28f9eca8eead815fc19e136c47"
+dependencies = [
+ "az",
+ "gmp-mpfr-sys",
+ "libc",
+]
+
+[[package]]
 name = "safe_arch"
 version = "0.5.2"
 source = "registry+https://github.com/rust-lang/crates.io-index"
diff --git a/Cargo.toml b/Cargo.toml
index 3995ad9..31cd1f1 100644
--- a/Cargo.toml
+++ b/Cargo.toml
@@ -7,3 +7,4 @@ edition = "2021"
 
 [dependencies]
 eframe = "0.19.0"
+rug = "1.17"
diff --git a/src/main.rs b/src/main.rs
index b2a8661..b8e6eb2 100644
--- a/src/main.rs
+++ b/src/main.rs
@@ -1,4 +1,6 @@
+use rug::{Complete, Integer};
 use eframe::egui;
+// use std::time::Instant;
 
 fn main() {
     let options = eframe::NativeOptions::default();
@@ -22,6 +24,8 @@ struct Application {
     element_check: Option<bool>,
     primitive_roots: Vec<u32>,
     state: State,
+
+    str_num: String,
 }
 
 impl Default for Application {
@@ -32,6 +36,8 @@ impl Default for Application {
             element_check: None,
             primitive_roots: Vec::new(),
             state: State::Idle,
+
+            str_num: String::from("20"),
         }
     }
 }
@@ -134,5 +140,82 @@ impl eframe::App for Application {
                 }
             }
         });
+        egui::Window::new("Задача №2").show(ctx, |ui| {
+            ui.horizontal(|ui| {
+                ui.label("Число: ");
+                ui.add(egui::TextEdit::singleline(&mut self.str_num));
+            });
+            if ui.button("Разложить на множители").clicked() {
+                let number = Integer::parse(&self.str_num).unwrap().complete();
+                let factors = factorize(&number);
+                println!("Множители: {:?}", factors);
+            }
+        });
+    }
+}
+
+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;
 }