Проверка большого нат. числа на простоту

Тема в разделе "Другие задачи", создана пользователем pastorixx, 24 май 2010.

Наш партнер Genesis Hackspace
  1. pastorixx

    pastorixx Active Member

    Регистрация:
    7 май 2010
    Сообщения:
    26
    Симпатии:
    0
    Проверка большого нат. числа на простоту
    Простое число это число которое делится только на само себя и на единицу. Большое число - например 16549875629787.
    Я как понимаю число надо записывать в строковый массив, потом делить столбиком на все числа от 2 до введенного. При этом делать проверку на остаток от деления. Проблема заключается в реализации деления столбиком. Почитав несколько форумов я примерно понял как должен выглядеть алгоритм, а вот с программной реализацией парюсь уже третий час и ничего хорошего написать не удалось.
    Помогите пожалуйста!
     
  2. DarkDaiver

    DarkDaiver Гость

    сделаю за умеренную плату
    ISQ: 412842920
    MAIL: darkdaiver777@gmail.com
     
  3. Dock1100

    Dock1100 :-]

    Регистрация:
    9 ноя 2009
    Сообщения:
    665
    Симпатии:
    0
    на форуме была похожая темя в разделе Pascal and Delphi, кажись.
    Тут есть алгоритм как найти найбольшое число для деления без остатка.

    Добавлено:
    должно работать.(для паскаля)
     
  4. hosm

    hosm * so what *

    Регистрация:
    18 май 2009
    Сообщения:
    2.445
    Симпатии:
    8
    Dock1100 для больших чисел - не факт, что код работчий, т.к. может быть переполнение.
     
  5. pastorixx

    pastorixx Active Member

    Регистрация:
    7 май 2010
    Сообщения:
    26
    Симпатии:
    0
    Код (Text):
    using System;
    using System.Collections.Generic;
    using System.ComponentModel;
    using System.Data;
    using System.Drawing;
    using System.Linq;
    using System.Text;
    using System.Windows.Forms;

    namespace Семестровая_задача_5_деление_
    {
    public partial class Form1 : Form
    {
    public Form1()
    {
    InitializeComponent();
    }

    private void button1_Click(object sender, EventArgs e)
    {
    textBox3.Clear();
    char[] X1 = new char[textBox1.Text.Length];//Делимое
    char[] Y1 = new char[textBox2.Text.Length];//Делитель
    int[] X = new int[textBox1.Text.Length];
    int[] Y = new int[textBox2.Text.Length];
    int[] Z = new int[textBox1.Text.Length];//Результат
    int[] A = new int[textBox2.Text.Length+1];
    int p=0,k = 0;
    bool b = false;

    X1 = textBox1.Text.ToCharArray();
    Y1 = textBox2.Text.ToCharArray();

    for (int i = 0; i < textBox1.Text.Length; i++)
    X[i] = Convert.ToInt32(X1[i])-48;
    for (int i = 0; i < textBox2.Text.Length; i++)
    Y[i] = Convert.ToInt32(Y1[i])-48;

    for (int i = 0; i < textBox1.Text.Length; i++)
    {
    for (int j = k; j < textBox2.Text.Length + p; j++)
    {
    A[j] = X[j];
    }
    for (int j = textBox2.Text.Length; j > 0; j--)
    {
    if (A[j] < Y[j])
    {
    if (j != 0)
    if (A[j - 1] != 0)
    {
    A[j - 1] = A[j - 1] - 1;
    A[j] = 10 + A[j] - Y[j];
    }
    else
    {
    //A[j - 1] = 9; //Если равно нулю то ....
    //if(A[j-2] != 0)
    //A[j - 2] = A[j - 2] - 1;
    }
    else
    {
    p = 1; b = false;
    k = textBox2.Text.Length;
    break;
    }
    }
    else
    A[j] = A[j] - Y[j];

    b = true; Z[i]++; p = 0;
    }
    if (b == true)
    for (int j = 0; j < textBox2.Text.Length; j++)
    if (A[j] == 0)
    {
    p++;
    }
    else
    break;
    }

    for (int i = 0; i < textBox1.Text.Length; i++)
    textBox3.Text += "" + Z[i];

    }
    }
    }
    Это просто деление без поиска простоты. На шаге "if (A[j] < Y[j])" пишет что индекс находится вне границ массива. Не могу понять почему(.
     
  6. pastorixx

    pastorixx Active Member

    Регистрация:
    7 май 2010
    Сообщения:
    26
    Симпатии:
    0
    Полагаю что Z++ я поместил не туда, вот только куда надо.....
     
  7. jlahcejlot

    jlahcejlot Гость

    Если че то число можно проверять не до самого числа, а до корня из этого числа, ибо если нет делителей до корня из n то и дальше не будет => n - простое

    Добавлено: Если че то число можно проверять не до самого числа, а до корня из этого числа, ибо если нет делителей до корня из n то и дальше не будет => n - простое
     
Загрузка...

Поделиться этой страницей