помогите написать программу для нахождения большого простого числа желательно на с++
буду очень благодарен=)

Изопропил,

например пока я смог получить из интервала от1 до 1000000000. это 53326267.
хотелось бы улучшить результаты.

mayton,

#include "stdafx.h"
#include<math.h>
#include<stdio.h>
#include<conio.h>
#include<time.h>
#include<tchar.h>

*
* 2009-05-02 Mayton - Добавлен динамич. массив
* Добавлен вывод статистики
* Добавлен замер времени
*/

int _tmain(int argc, _TCHAR* argv[])
{
int time1=time(NULL);


int limit = 1000000000;
int sqr_lim;
//bool is_prime[1001];
bool *is_prime = new bool[limit+1];
int x2, y2;
int i, j;
int n;

// Инициализация решета
sqr_lim = (int)sqrt((long double)limit);
for (i = 0; i <= limit; i++) is_prime[i] = false;
is_prime[2] = true;
is_prime[3] = true;

// Предположительно простые - это целые с нечетным числом
// представлений в данных квадратных формах.
// x2 и y2 - это квадраты i и j (оптимизация).
x2 = 0;
for (i = 1; i <= sqr_lim; i++) {
x2 += 2 * i - 1;
y2 = 0;
for (j = 1; j <= sqr_lim; j++) {
y2 += 2 * j - 1;
n = 4 * x2 + y2;
if ((n <= limit) && (n % 12 == 1 || n % 12 == 5))
is_prime[n] = !is_prime[n];

// n = 3 * x2 + y2;
n -= x2; // Оптимизация
if ((n <= limit) && (n % 12 == 7))
is_prime[n] = !is_prime[n];

// n = 3 * x2 - y2;
n -= 2 * y2; // Оптимизация
if ((i > j) && (n <= limit) && (n % 12 == 11))
is_prime[n] = !is_prime[n];
}
}

// Отсеиваем квадраты простых чисел в интервале [5, sqrt(limit)].
// (основной этап не может их отсеять)
for (i = 5; i <= sqr_lim; i++) {
if (is_prime[i]) {
n = i * i;
for (j = n; j <= limit; j += n) {
is_prime[j] = false;
}
}
}

// Вывод списка простых чисел в консоль.

int primecount=0;
for (i = 2; i <= limit; i++) {
if (is_prime[i]) {
//printf(", %d", i);
primecount++;
}
}

int time2=time(NULL);

printf("\nAtkin 1.0 statistics :\n");
printf(" Interval : [2..%d]\n", limit);
printf(" Primes detected : %d\n", primecount);
printf(" Time elapsed : %d sec\n\n", time2-time1);

delete[] is_prime;
getch();
return 0;
}

вот програмка которая находит самое большое простое число до 1.000.000.000. хотелось бы находить до 10.000.000.000
. короче надо улучщить код или написать другую программу.

maytonсерегй, там чуть ниже я где-то еще один исходник приаттачивал с поддержкой uint64 расчётов и
с быстрой целочисленной функцией sqrt без использования double типов.
unsigned int isqrt32(unsigned int x)
{
unsigned int x1;
int s, g0, g1;
if (x <= 1) return x;
s = 1;
x1 = x - 1;
if (x1 > 65535) { s+=8; x1>>=16;}
if (x1 > 255) { s+=4; x1>>=8;}
if (x1 > 15) { s+=2; x1>>=4;}
if (x1 > 3) { s+=1; }
g0 = 1<<s;

g1 = (g0 + (x >> s)) >> 1;
while(g1 < g0)
{
g0 = g1;
g1 = (g0 + (x/g0)) >> 1;
}
return g0;
}

вот этот да?
куда его вставить?

Abstractionсерегй,

Ну...
как это? и почему -1?

maytonФокус такой (с) Госпожа Беладонна.

Отрицательное signed (-1) похоже на максимальное unsigned.
так signet long long int limit=-1 или как?
#include<limits.h>

maytonНу кагбе вместо квадратного корня. Ты определись с разрядностью. Этот сорс заточен только под UINT32.

Если ты используешь UINT64 (возм. long) то имплементацию надо будет переделать. Это, если
мне не изменяет память метод Ньютона. Оригинал я возможно брал из книги Генри Уоррена
- Алгоритмические трюки.

пока подумаю как это сделать...

серегйmayton,

#include "stdafx.h"
#include<math.h>
#include<stdio.h>
#include<conio.h>
#include<time.h>
#include<tchar.h>

*
* 2009-05-02 Mayton - Добавлен динамич. массив
* Добавлен вывод статистики
* Добавлен замер времени
*/

int _tmain(int argc, _TCHAR* argv[])
{
int time1=time(NULL);


int limit = 1000000000;
int sqr_lim;
//bool is_prime[1001];
bool *is_prime = new bool[limit+1];
int x2, y2;
int i, j;
int n;

// Инициализация решета
sqr_lim = (int)sqrt((long double)limit);
for (i = 0; i <= limit; i++) is_prime[i] = false;
is_prime[2] = true;
is_prime[3] = true;

// Предположительно простые - это целые с нечетным числом
// представлений в данных квадратных формах.
// x2 и y2 - это квадраты i и j (оптимизация).
x2 = 0;
for (i = 1; i <= sqr_lim; i++) {
x2 += 2 * i - 1;
y2 = 0;
for (j = 1; j <= sqr_lim; j++) {
y2 += 2 * j - 1;
n = 4 * x2 + y2;
if ((n <= limit) && (n % 12 == 1 || n % 12 == 5))
is_prime[n] = !is_prime[n];

// n = 3 * x2 + y2;
n -= x2; // Оптимизация
if ((n <= limit) && (n % 12 == 7))
is_prime[n] = !is_prime[n];

// n = 3 * x2 - y2;
n -= 2 * y2; // Оптимизация
if ((i > j) && (n <= limit) && (n % 12 == 11))
is_prime[n] = !is_prime[n];
}
}

// Отсеиваем квадраты простых чисел в интервале [5, sqrt(limit)].
// (основной этап не может их отсеять)
for (i = 5; i <= sqr_lim; i++) {
if (is_prime[i]) {
n = i * i;
for (j = n; j <= limit; j += n) {
is_prime[j] = false;
}
}
}

// Вывод списка простых чисел в консоль.

int primecount=0;
for (i = 2; i <= limit; i++) {
if (is_prime[i]) {
//printf(", %d", i);
primecount++;
}
}

int time2=time(NULL);

printf("\nAtkin 1.0 statistics :\n");
printf(" Interval : [2..%d]\n", limit);
printf(" Primes detected : %d\n", primecount);
printf(" Time elapsed : %d sec\n\n", time2-time1);

delete[] is_prime;
getch();
return 0;
}

вот програмка которая находит самое большое простое число до 1.000.000.000. хотелось бы находить до 10.000.000.000
. короче надо улучщить код или написать другую программу.
программа выводит 53326267
это не простое число ... что делать?

maytonНет такого числа.

В окрестности этого числа (53326267) метод Аткина выдаёт последовательность

#include "stdafx.h"
#include<math.h>
#include<stdio.h>
#include<conio.h>
#include<time.h>
#include<tchar.h>

int _tmain(int argc, _TCHAR* argv[])
{
int time1=time(NULL);


int limit = 100000000;
int sqr_lim;
//bool is_prime[1001];
bool *is_prime = new bool[limit+1];
int x2, y2;
int i, j;
int n;

// Инициализация решета
sqr_lim = (int)sqrt((long double)limit);
for (i = 0; i <= limit; i++) is_prime[i] = false;
is_prime[2] = true;
is_prime[3] = true;

// Предположительно простые - это целые с нечетным числом
// представлений в данных квадратных формах.
// x2 и y2 - это квадраты i и j (оптимизация).
x2 = 0;
for (i = 1; i <= sqr_lim; i++) {
x2 += 2 * i - 1;
y2 = 0;
for (j = 1; j <= sqr_lim; j++) {
y2 += 2 * j - 1;
n = 4 * x2 + y2;
if ((n <= limit) && (n % 12 == 1 || n % 12 == 5))
is_prime[n] = !is_prime[n];

// n = 3 * x2 + y2;
n -= x2; // Оптимизация
if ((n <= limit) && (n % 12 == 7))
is_prime[n] = !is_prime[n];

// n = 3 * x2 - y2;
n -= 2 * y2; // Оптимизация
if ((i > j) && (n <= limit) && (n % 12 == 11))
is_prime[n] = !is_prime[n];
}
}

// Отсеиваем квадраты простых чисел в интервале [5, sqrt(limit)].
// (основной этап не может их отсеять)
for (i = 5; i <= sqr_lim; i++) {
if (is_prime[i]) {
n = i * i;
for (j = n; j <= limit; j += n) {
is_prime[j] = false;
}
}
}

// Вывод списка простых чисел в консоль.

int primecount=0;
for (i = 2; i <= limit; i++) {
if (is_prime[i]) {
//printf(", %d", i);
primecount++;
}
}

int time2=time(NULL);

printf("\nAtkin 1.0 statistics :\n");
printf(" Interval : [2..%d]\n", limit);
printf(" Primes detected : %d\n", primecount);
printf(" Time elapsed : %d sec\n\n", time2-time1);

delete[] is_prime;
getch();
return 0;
}

Ищи у себя ошибку. вот программа. но она выдает 53326267, но это не простое число=(
как ты вывел эти числа? можешь написать эту программу?

maytonОни (как ни странно) лежат в массиве is_prime.
Не обижайся но у меня нет интереса тебе помогать.
Ты объективно очень слабый кодер в С++ и тебе
еще рано писать (и даже использовать готовые
исходники). Подучи сначала основы С++

Всего хорошего.

так это твоя программа и у тебя тоже это число вывелось...
мы только начали с++ изучать так что это не моя вина что я плохо разбиаюсь в функциях и т д.

mayton http://ru.wikipedia.org/wiki/%D0%A0%D0%B5%D1%88%D0%B5%D1%82%D0%BE_%D0%90%D1%82%D0%BA%D0%B8%D0%BD%D0%B0
решето аткина... у меня работает только до миллиона...
как увеличить интервал?