From 4a8088e904fe46d842d37d75bacb3ed6092b6e12 Mon Sep 17 00:00:00 2001
From: Andrew Guschin <guschin.drew@gmail.com>
Date: Mon, 26 Sep 2022 03:08:00 +0400
Subject: =?UTF-8?q?=D0=94=D0=BE=D0=B1=D0=B0=D0=B2=D0=BB=D0=B5=D0=BD=D0=B0?=
 =?UTF-8?q?=20=D1=80=D0=B5=D0=B0=D0=BB=D0=B8=D0=B7=D0=B0=D1=86=D0=B8=D1=8F?=
 =?UTF-8?q?=20=D0=B2=D1=82=D0=BE=D1=80=D0=BE=D0=B9=20=D0=BB=D0=B0=D0=B1?=
 =?UTF-8?q?=D0=BE=D1=80=D0=B0=D1=82=D0=BE=D1=80=D0=BD=D0=BE=D0=B9?=
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8
Content-Transfer-Encoding: 8bit

---
 src/main.rs | 83 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 83 insertions(+)

(limited to 'src/main.rs')

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;
 }
-- 
cgit v1.2.3