VPF::Простые числа... - Форум программистов

Tripl-X

Дата 24.2.2005, 22:01 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 47
Регистрация: 29.12.2004

Репутация: нет
Всего: 1

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

если можно - исходник на С++.

Наставник

Дата 25.2.2005, 01:21 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 327
Регистрация: 4.11.2004

Репутация: нет
Всего: 15

Цитата(Tripl @ 24.2.2005, 22:01)

как сформировать массив из простых чисел, не больших заданного...

Самый простой и оптимальный способ - решето ЭРАТОСФЕНА

Код


#include <iostream.h>
static const int N=1000; // поиск простых чисел не превышающего числа 1000
int main()
{
  int i, a[N];
  for(i=2; i<N; i++) a[i]=1; // предположим, что все числа до N простые
  for(i=2;i<N;i++)
    if(a[i])
      for(int j=i; j*i<N; j++) a[i*j]=0; // число не простое, т.к. распадается на множители j и i, поэтому в массив a[i] записываем "0" 
  for(i=2;i<N;i++)
    if(a[i]) // если 1, то простое число
      cout<<" "<<i;
  cout<<endl;
}

Цитата(Tripl @ 24.2.2005, 22:01)

массив простых делителей(всех) числа...

итак в массиве a[i] находятся простые числа, от 1 до N, в тех местах где 1.

Код


static const int chislo=1000; // найдем все простые делители числа 1000
int i,j,b[chislo];
j=0;
for(i=1;i<N;i++)
  if(a[i])
     if(chislo%i==0)
     {
       b[j]=i;
       j++;
     }
// итак, в массиве b[0...j-1] хранятся все делители числа 1000.

Удачи.

Это сообщение отредактировал(а) Наставник - 25.2.2005, 02:44

--------------------

Богатство языка определяет широту мысли
Персональный сайт >>

cardinal

Дата 25.2.2005, 02:37 (ссылка)

(нет голосов)

Загрузка ...

Инженер

Профиль
Группа: Экс. модератор
Сообщений: 6003
Регистрация: 26.3.2002
Где: Германия

Репутация: 5
Всего: 99

Вот алгоритм на VB, но вроде все должно быть понятно - он простой:
VB-VB-002120

--------------------

Немецкая оппозиция потребовала упростить натурализацию иммигрантов
В моем блоге: Разные истории из жизни в Германии

"Познание бесконечности требует бесконечного времени, а потому работай не работай - все едино". А. и Б. Стругацкие

EKoshelev

Дата 13.4.2005, 09:48 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 509
Регистрация: 1.9.2004

Репутация: нет
Всего: нет

А я на дельфе давно уже прогу надолбил. Она минут за 15 (может меньше, не помню) генерит текстовый файл со всеми простыми числами в пределах первых 80 000 000. По Эратосфену делал. 400 МГц.

Это сообщение отредактировал(а) EKoshelev - 13.4.2005, 09:51

--------------------

Вежливым и адекватным предлагаю общаться на "ты".

@lex

Дата 14.4.2005, 11:57 (ссылка)

(нет голосов)

Загрузка ...

Шустрый

Профиль
Группа: Участник
Сообщений: 82
Регистрация: 3.2.2004
Где: Москва

Репутация: нет
Всего: нет

Цитата

Есть ли какая-нибудь формула простого числа?

если ее кто-нить в ближайшее время получит, то начнется такой бардак.... smile

многие криптографические алгоритмы на это строятся...

poor_yorik

Дата 19.4.2005, 21:47 (ссылка)

(нет голосов)

Загрузка ...

Шустрый

Профиль
Группа: Участник
Сообщений: 148
Регистрация: 12.1.2005
Где: Общаги г. Киева

Репутация: 3
Всего: 8

А я как знаю, так умные дяди-ученые ( smile

) доказали, что не существует и не может существовать простой формулы для вычисления простых чисел. Уж больно они умные ив распределеятся на числовом множестве довольно неоднооборазно. Хотя какая то гармония есть.
Вот например между числами а и 2*а+1, где а любое натуральное есть хотя бы одно простое число. Но это особо не помогает, поэтому приходится довольствоваться решетом Эратосфена. smile

--------------------

Семь раз отмерь, один раз - откомпиль.... Семь раз отпей, один раз - отлей... Семь раз отъешь, один раз - не жадничай и другим дай...

0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема \| Алгоритмы \| Следующая тема »