0 / 0 / 0
Регистрация: 25.01.2014
Сообщений: 14
1

Поиск простых чисел

21.04.2014, 02:58. Показов 5015. Ответов 3
Метки нет (Все метки)

Знаю, что тема избитая, но решил написать алгоритм поиска простых чисел.

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int j,i,k /*количество простых*/                ,nech,prime[1000];
bool a;
k=1;  nech=3;  prime[1]=2;// Одно простое число - 2, первое нечётное - 3
for(j=1;j<1000;j++){ // Смотрим 1000 нечётных чисел
        for(i=1;i<=k;i++){  // Смотрим столько раз, сколько простых чисел в массиве
                if(nech%prime[i]==0){ // Если нечётное число делится на простое число без остатка
                        a=true;     } // Делаем а положительным
                         }
        if(a==true)                   // Если а положительное, т.е нечётное число составное
        {nech=nech+2;}                // Смотрим следующее нечётное число
        else {cout<<nech<<",  "; k=k+1; prime[k]=nech; nech=nech+2;} //А если простое, то занесём его в массив простых чисел и посмотрим на следующее нечётное число число
                         }
 
                          Sleep(3000);
 
}
Выводит лишь 3 первых простых числа, хотя должна перебрать 1000 нечётных чисел.
Прошу помощи нахождения ошибки в моём коде.
__________________
Помощь в написании контрольных, курсовых и дипломных работ, диссертаций здесь
0
Лучшие ответы (1)
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
21.04.2014, 02:58
Ответы с готовыми решениями:

Поиск простых чисел
необходимо найти все простые числа от 1 до 100. Вот я написал код: #include &lt;iostream&gt; #include...

Поиск простых чисел
помогите пожалуйста с заданием напишите программу которая при помощи двух вложенных циклов for и...

Поиск простых чисел
#include &lt;iostream&gt; #include &lt;stdio.h&gt; #include &lt;locale.h&gt; using namespace std; int y;...

Поиск простых чисел
Почему мне возвращает просто непарные числа? в чем загвоздка #include &lt;iostream&gt; bool...

3
87 / 68 / 19
Регистрация: 07.03.2011
Сообщений: 169
21.04.2014, 03:06 2
А чем вам решето Эратосфена не нравится?
2
153 / 136 / 45
Регистрация: 15.02.2010
Сообщений: 745
21.04.2014, 15:41 3
Лучший ответ Сообщение было отмечено Xerotico как решение

Решение

Решето Эратосфена: если натуральное число не делится ни на какие простые числа меньшие за него, то оно само является простым.
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include <iostream>
#include <iomanip>
using namespace std;
int main()
{
int N;
cin >> N; //количество простых чисел
 int *M = new int [N];//создание динамического массива 
M[0]=2;//2 - первое простое число, занесённое в массив
int p=3;//p- очередное число, проверяемое на "простоту"
int n;//n- индекс последнего простого числа в массиве
for (n=1; n<N; n++)
{
a:     for (int i = 0; i<=n; i++)//для каждого элемента массива простых чисел...
       {
             if (M[i]<=p/2 && p%M[i]==0) //(делитель не может быть больше половины числа р) если p-не простое 
             {
                    p++;//то переходим к следующему числу
                    goto a;//и заново проверяем его на делимость на все найденные простые
             }
       }
//из цикла помеченного как а: выйдет в любом слуае после нахождения очередного простого р    
M[n]=p;//записываем найденное простое в массив
p++;//переходим к очередному числу для проверки на "простоту"
}
//вывод массива простых чисел
for (int i = 0; i<N; i++) 
   cout << M[i] << " ";
 delete [] M; //освобождаем память занятую под динамический массив
 system ("pause");
 return 0;
 }
1
0 / 0 / 0
Регистрация: 25.01.2014
Сообщений: 14
21.04.2014, 15:56  [ТС] 4
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int j,i,k /*количество простых*/                ,nech,prime[1000];
for(j=1;j<1000;j++)
prime[j]=0;
bool a;
k=1;  nech=3;  prime[1]=2;// Одно простое число - 2, первое нечётное - 3
for(j=1;j<1000;j++){ // Смотрим 1000 нечётных чисел
        for(i=1;i<=k;i++){  // Смотрим столько раз, сколько простых чисел в массиве
                if(nech%prime[i]==0){ // Если нечётное число делится на простое число без остатка
                        a=true;     } // Делаем а положительным
                         }
        if(a==true)                   // Если а положительное, т.е нечётное число составное
        {nech=nech+2; [B]a=false;[/B]}                // Смотрим следующее нечётное число
        else {cout<<nech<<'\n'; k=k+1; prime[k]=nech; nech=nech+2; [B]a= false[/B];} //А если простое, то занесём его в массив простых чисел и посмотрим на следующее нечётное число число
                         }
 
Sleep(10000);
Ошибка найдена, всем спасибо за участие.
0
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
21.04.2014, 15:56
Помогаю со студенческими работами здесь

Поиск простых чисел
3. Разработать программу поиска простых чисел в отрезке (1..N) целых положительных чисел. Программа...

Поиск простых чисел
Народ, в программе нужно из введённых чисел найти и вывести простые числа(т.е. 2,3,5,7,11,13... и...

поиск простых чисел
Как найти количество цифр n- значных чисел, у которых сумма любых двух соседних цифр является...

Поиск простых чисел
Всем привет, прохожу книгу Шилдта и остановился на программе:...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
4
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2022, CyberForum.ru