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

[pastorixx]

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

 

[DarkDaiver]

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

 

[Dock1100]

на форуме была похожая темя в разделе Pascal and Delphi, кажись.
Тут есть алгоритм как найти найбольшое число для деления без остатка.

Добавлено:

????, да тут не знание Паскаля имелось в виду, я ж не придиралась там к to/downto или лишнему декременту счетчика цикла...
там суть коммента такая: логичное предположение о том, что максимальный делитель получится либо при делении sum на 2 (если число sum делится на 2), либо будет меньше целой части от деления числа sum на 2 (ну, в частности, будет равен 1, если других искомых делителей нет), поэтому в общем случае просматривать от sum -1 не совсем рационально (неэффективно).
Ну, в общем, нужно нечто подобное такому:

result := 1;
if sum>3 then // числа 1-3 - простые, не нужно проверять делители
for i := sum div 2 downto 2 do
if (sum mod i) = 0 then
begin
result := i;
break; // или если нет такого i:=2; т.е. цель-выйти из цикла
end;
if (result = 1)
writeln('no')
else
writeln(result);

просто вчера не было времени описать нормально (

должно работать.(для паскаля)

 

[hosm]

Dock1100 для больших чисел - не факт, что код работчий, т.к. может быть переполнение.

 

[pastorixx]

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])" пишет что индекс находится вне границ массива. Не могу понять почему(.

 

[pastorixx]

Полагаю что Z++ я поместил не туда, вот только куда надо.....

 

[jlahcejlot]

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

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