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

[PastoriXx]

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

[mrChester]

Если будешь делить столбиком, проверка будет длиться очень долго. У меня есть реализованный на С++ алгоритм Миллера-Рабина с использованием технологии GMP, числа порядка 10^1200 проверяет несколько секунд

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "gmp.h"
#include <time.h>
#include<conio.h>

#pragma comment(lib,"gmp.lib")
#define COMPOSITE        0
#define PROBABLE_PRIME   1


int miller_rabin_pass(mpz_t a, mpz_t n) {
    int i, s, result;
    mpz_t a_to_power, d, n_minus_one;

    mpz_init(n_minus_one);
    mpz_sub_ui(n_minus_one, n, 1);

    s = 0;
    mpz_init_set(d, n_minus_one);
    while (mpz_even_p(d)) {
        mpz_fdiv_q_2exp(d, d, 1);
        s++;
    }


    mpz_init(a_to_power);
    mpz_powm(a_to_power, a, d, n);
    if (mpz_cmp_ui(a_to_power, 1) == 0)  {
        result=PROBABLE_PRIME; goto exit;
    }
    for(i=0; i < s-1; i++) {
        if (mpz_cmp(a_to_power, n_minus_one) == 0) {
            result=PROBABLE_PRIME; goto exit;
        }
        mpz_powm_ui (a_to_power, a_to_power, 2, n);
    }
    if (mpz_cmp(a_to_power, n_minus_one) == 0) {
        result=PROBABLE_PRIME; goto exit;
    }
    result = COMPOSITE;

exit:
    mpz_clear(a_to_power);
    mpz_clear(d);
    mpz_clear(n_minus_one);
    return result;
}


int miller_rabin(mpz_t n, gmp_randstate_t rand_state) {
    mpz_t a;
    int repeat;
    mpz_init(a);
    for(repeat=0; repeat<20; repeat++) {
        do {
            mpz_urandomm(a, rand_state, n);
        } while (mpz_sgn(a) == 0);
        if (miller_rabin_pass(a, n) == COMPOSITE) {
            return COMPOSITE;
        }
    }
    return PROBABLE_PRIME;
}


int main(int argc, char* argv[]) 
{
    mpz_t n, max, two, p;
    gmp_randstate_t rand_state;
	gmp_randinit_default(rand_state);
    gmp_randseed_ui (rand_state, time(NULL));
	int bit;
	clock_t start, finish;

	bool menu = true;
    while (menu)
    {
		printf("\n\n1: proverit' chislo na prostotu\n2: sgenerirovat' prostoe chislo\n3: proverit' sgenerirovannoe chislo\n4: vihod\n");
		switch(getch())
		{
		case '1':
			printf ("Proverka...");
			start = clock();
			mpz_init_set_str(n, "1586035379198363215476851652230960441533743808536642643444663584989548225749086407213962337839531871593467593692439157280823229803937229469314959215033802075792514489392054314317511672883916851504744961315365975347518851845564597396383196423247887001669679576843618063885810175572024722509007561845259219770373024113303725866525780618564467808235297170203187284765914883961827638955723465873285633425820982513526545718153929798622619113857453123899474185436423117641915544884656306881977312338564065425648950529140702603947557996097291715599019821456811275762872041266127737545596343859468110186533568132501833314555320523623829030956919510159515937481551881689418842152135548959407039295406770093761406529248014362248772909628926879437486026972062502035348208726018856363742754044711515963767825902647927125123139557553262361027102300683553743123296847959476770337971105539913277026372334707206054027430802075839708163206871608805218035576714419874104272460539659037866147662225859663133693754196609583901713602315183087215148138098802557658971080722687632690975235470048133753783200960218093327088770872613267600328981756153336910298702583427436584391111736370975007180206128422596673638175658973141514312469132081471817525346893317", 10);
	        puts(miller_rabin(n, rand_state) == PROBABLE_PRIME ? "PRIME" : "COMPOSITE");
			finish = clock();
			printf("Vremya: %2.3f sec",double(finish-start)/ CLOCKS_PER_SEC);
			break;
		case '2':
			printf ("\nVvedite razmer chisla v bitah: ");
			scanf ("%d",&bit);			
			mpz_init(max);
			mpz_init_set_ui(two, 2);
			mpz_mul_2exp(max, two, bit);//atoi(argv[2])+1);
	        mpz_init(p);
			bool pr; 
			start = clock();
	        do 
			{
			    mpz_urandomm(p, rand_state, max);
				if (!(mpz_even_p(p)) && !(mpz_fdiv_ui(p, 3) == 0) && !(mpz_fdiv_ui(p, 5) == 0) &&
					!(mpz_fdiv_ui(p, 7) == 0) && !(mpz_fdiv_ui(p, 11) == 0) && !(mpz_fdiv_ui(p, 13) == 0) &&
					(miller_rabin(p, rand_state) == PROBABLE_PRIME)) break; 
			} while (true);
			char strs[4096];
			 mpz_get_str(strs, 10, p);
	        puts(strs);
			FILE* out;
			out = fopen ("out.txt","w");		
			fprintf(out,"%s",strs);
			finish = clock();
			fprintf(out,"Vremya: %2.3f sec",double(finish-start)/ CLOCKS_PER_SEC);
			printf("Vremya: %2.3f sec",double(finish-start)/ CLOCKS_PER_SEC);
			fclose(out);
			break;
		case '3':
			printf ("\nProverka...\n");
			start = clock();
			puts(miller_rabin(p, rand_state) == PROBABLE_PRIME ? "PRIME" : "COMPOSITE");
			finish = clock();
			printf("Vremya: %2.3f sec",double(finish-start)/ CLOCKS_PER_SEC);
			break;
		case '4':
			menu = false;
			break;
		}	
	}//while
   return 0;
}

[mrChester]

Есть еще пример без использования GMP, но там код огромный, да и разобраться в нем будет не просто

[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]

уже исправил

int[] A = new int[textBox2.Text.Length]; //убрал +1
...
for (int j = textBox2.Text.Length - 1; j >= 0; j--) // добавил -1
{
    if (A[j] < Y[j]) ...

хотя пока правильно не делит(

[PastoriXx]

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