Форум программистов, компьютерный форум, киберфорум
Наши страницы
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
 
Рейтинг 4.80/5: Рейтинг темы: голосов - 5, средняя оценка - 4.80
Noob1233
1 / 1 / 0
Регистрация: 04.02.2014
Сообщений: 45
1

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

20.10.2014, 23:32. Просмотров 942. Ответов 25
Метки нет (Все метки)

необходимо найти все простые числа от 1 до 100. Вот я написал код:
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
#include <iostream>
#include <string>
#include <cstdlib>
#include "stdafx.h"
 
int main() {
    double ost;
    vector <int> m();
    int b=0,c,n;
    for(int i=0,i<100,i++) {
        while(b<i) {
            c=i%b;
            b++;
            if(c==0) {
                n++;
            }
                    }
            if(n==2) {
                i=m.push_back;
            }
    }
    int z;
    while(z<size.m){
        z++;
        cout<<vector m(z);
    }
}
Но не совсем понял операции производимые с вектором. Подскажите, правильно ли я вообще написал код?
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
20.10.2014, 23:32
Ответы с готовыми решениями:

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

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

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

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

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

25
alsav22
5442 / 4837 / 831
Регистрация: 04.06.2011
Сообщений: 13,587
20.10.2014, 23:40 2
C++
1
vector <int> m();
Это не вектор.
C++
1
vector <int> m;
Цитата Сообщение от Noob1233 Посмотреть сообщение
Подскажите, правильно ли я вообще написал код?
Компилятор, что пишет?
0
TheCalligrapher
С чаем беда...
Эксперт CЭксперт С++
4772 / 2429 / 679
Регистрация: 18.10.2014
Сообщений: 4,148
20.10.2014, 23:46 3
Цитата Сообщение от Noob1233 Посмотреть сообщение
Подскажите, правильно ли я вообще написал код?
Написана полнейшая белиберда. О "правильно ли я написал код" говорить рано - никакого "кода" пока нет. Без знания элементарнейшего синтаксиса языка пытаться писать код совершенно бесполезно. Надо идти читать книжки.
0
ValeryS
Модератор
7271 / 5525 / 692
Регистрация: 14.02.2011
Сообщений: 18,714
20.10.2014, 23:47 4
Цитата Сообщение от Noob1233 Посмотреть сообщение
Подскажите, правильно ли я вообще написал код?
конечно нет
Цитата Сообщение от Noob1233 Посмотреть сообщение
int b=0,
Цитата Сообщение от Noob1233 Посмотреть сообщение
c=i%b;
деление на 0!!!
и какой остаток хочешь получить при делении на 0 и 1???
Цитата Сообщение от Noob1233 Посмотреть сообщение
необходимо найти все простые числа от 1 до 100.
1 не является простым числом
самое маленькое простое число 2
так что
Цитата Сообщение от Noob1233 Посмотреть сообщение
for(int i=0,i<100,i++)
смысла не имеет цикл нужно начинать с 2
и этих тем на форуме куча
вот одна из них
Быстрая проверка натурального числа на простоту
самая умная
0
Nevermind_qqq
72 / 58 / 41
Регистрация: 25.06.2014
Сообщений: 358
20.10.2014, 23:48 5
Noob1233, куча ошибок в синтаксисе , почитай хотя бы базовую литературу(уже используешь вектор но не правильно задаешь цикл for), куча ненужных переменных, в моем представлении это должно выглядеть так
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
#include <iostream>
#include <string>
#include <cstdlib>
#include <vector>
 
int main() {
    bool flag;
    for (int i = 1; i <= 100; i++)
    {
        flag = false;
        for (int j = 2; j < i; j++)
        {
            if (i%j == 0)
            {
                flag = true;
            }
        }
        if (!flag)
        {
            std::cout << i << "-simple" << std::endl;
        }
    }
    system("pause");
    return 0;
}
0
ValeryS
Модератор
7271 / 5525 / 692
Регистрация: 14.02.2011
Сообщений: 18,714
21.10.2014, 00:02 6
Цитата Сообщение от Nevermind_qqq Посмотреть сообщение
в моем представлении это должно выглядеть так
во первых 1 проверять нет смысла она не простая, во вторых нет смысла проверять делимость до самого числа, достаточно до корня
в третьих четные не являются простыми
в четвертых ели нашел одну делимость нет смысла крутить дальше число не простое

из всего следует вот такой код
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
int main() {
  bool flag;
    std::cout  << "2-simple" << std::endl;
     std::cout << "3-simple" << std::endl;
 
  for (int i = 5; i <= 100; i+=2)
    {
     flag = false;
       for (int j = 3; j*j <=i; j+=2)
        {
            if (i%j == 0)
            {
                flag = true;
               break;
            }
        }
        if (!flag)
        {
            std::cout << i << "-simple" << std::endl;
        }
    }
    system("pause");
    return 0;
}
это еще не самый оптимальный вариант
1
Nevermind_qqq
72 / 58 / 41
Регистрация: 25.06.2014
Сообщений: 358
21.10.2014, 20:58 7
ValeryS, мб еще все простые числа с клавиатуры ввести?
C++
1
2
std::cout  << "2-simple" << std::endl;
     std::cout << "3-simple" << std::endl;
и после этого говорить, что у меня не оптимальный код...
0
Байт
Эксперт C
18523 / 12029 / 2507
Регистрация: 24.12.2010
Сообщений: 24,301
21.10.2014, 21:28 8
Цитата Сообщение от ValeryS Посмотреть сообщение
это еще не самый оптимальный вариант
Из простейшего, что мне удалось сделать, это разбить числа на тридцатки. Решето Эратосфена для тридцатки(кроме 1-й) прекрасно влезает в 1 байт. И не надо проверять на 3, 5. Конечно, первую тридцатку приходится выводить вручную...

Не по теме:

Цитата Сообщение от Nevermind_qqq Посмотреть сообщение
и после этого говорить, что у меня не оптимальный код...
Шутить изволите?

0
Nevermind_qqq
21.10.2014, 21:31
  #9

Не по теме:

Байт, я считаю, что "алгоритм" и "выводить вручную" - это абсолютно разные понятия, выводить вручную много ума не надо

0
Байт
Эксперт C
18523 / 12029 / 2507
Регистрация: 24.12.2010
Сообщений: 24,301
21.10.2014, 22:17 10
Цитата Сообщение от Nevermind_qqq Посмотреть сообщение
я считаю, что "алгоритм" и "выводить вручную" - это абсолютно разные понятия,
У вас какое-то странное понимание слова "алгоритм"
Алгори́тм — набор инструкций, описывающих порядок действий исполнителя для достижения результата решения задачи за конечное число действий.
Программа
C
1
2
static int prim[] = { 2,3,5,7,11,13,17,19,23,29,31,37, 0 };
for(i=0;prim[i];i++) printf("%d\n", prim[i])
полностью соответствует приведенному определению, если задачей является вывод простых до 40.
А по поводу эффективности вашего алгоритма, согласитесь, там еще много возможностей для улучшения...
0
_Ivana
3233 / 1861 / 234
Регистрация: 01.03.2013
Сообщений: 5,091
Записей в блоге: 5
22.10.2014, 04:58 11
Nevermind_qqq, у вас адЪ и Израиль в коде. Сделайте сравнительные тесты вашего кода и кода ValeryS не до 100 а до нормального большого числа. Всем здравомыслящим участникам понятно, каков будет результат сравнения.
0
ValeryS
Модератор
7271 / 5525 / 692
Регистрация: 14.02.2011
Сообщений: 18,714
22.10.2014, 16:12 12
Цитата Сообщение от Nevermind_qqq Посмотреть сообщение
мб еще все простые числа с клавиатуры ввести?
все????
или в дапазоне?
если в диапазоне, то делают так, и очень часто
"Табличный метод"
у Байт, в пределах 40 этот метод прекрасно показан
Цитата Сообщение от Nevermind_qqq Посмотреть сообщение
выводить вручную много ума не надо
если учесть,что нужно, как минимум, эти числа знать
Цитата Сообщение от Nevermind_qqq Посмотреть сообщение
и после этого говорить, что у меня не оптимальный код...
он не только не оптимальный, он неправильный
покажет что 2 непростое
двойка единственное четное простое число
где и как обрабатывается это исключение?

Добавлено через 7 часов 21 минуту
Цитата Сообщение от Байт Посмотреть сообщение
Решето Эратосфена для тридцатки(кроме 1-й) прекрасно влезает в 1 байт.
вот здесь непонятно
битовый поля? но как паковывать?
вот например
30 31 32 33 34 35 36 37 38 39 40 41
остаются числа 31 37 41
как их упаковать в байт?
0
Nevermind_qqq
72 / 58 / 41
Регистрация: 25.06.2014
Сообщений: 358
22.10.2014, 18:42 13
ValeryS, мб надо сначала запустить прежде чем говорить, что неправильно считает(число 2 вполне определяется), единственное место, где я ошибся, это в строчке
C++
1
for (int i = 1; i <= 100; i++)
1 заменить на 2, просто забыл что 1 исключение(в то же время 2 ни капли не исключение для алгоритма, т. к. четность-нечетность не проверяется)

Добавлено через 8 минут
Байт, в том примере, что вы привели, исполнителем по факту был человек(вы естественно) , который эти числа ввел, т.к. решение было получено до того как компьютер обработал данные и вывел массив на экран
0
ValeryS
Модератор
7271 / 5525 / 692
Регистрация: 14.02.2011
Сообщений: 18,714
22.10.2014, 18:53 14
Цитата Сообщение от Nevermind_qqq Посмотреть сообщение
мб надо сначала запустить прежде чем говорить,
где я должен запустить?
есть готовый код?
Цитата Сообщение от Nevermind_qqq Посмотреть сообщение
т. к. четность-нечетность не проверяется)
а деление?(остаток)
Цитата Сообщение от Nevermind_qqq Посмотреть сообщение
число 2 вполне определяется
согласен, сглупил
Цитата Сообщение от Nevermind_qqq Посмотреть сообщение
for (int j = 2; j < i; j++)
при i не войдет в цикл, значит не проверится
не заметил что условие строгое

насчет остального есть возражения?

допустим тебе нужно не до 100 а до 264-1
для упрощения не вывести все а проверить число
сколько итераций у тебя будет?
264-2 итерации примерно 16*1018
одна итерация 1/1000000000 сек(это я сгоряча) 10-9сек
сколько считать будет ??? по моему 16*109 секунд

а у меня 231 примерно 2*109
2*109/ 109=2 секунды
0
Байт
Эксперт C
18523 / 12029 / 2507
Регистрация: 24.12.2010
Сообщений: 24,301
22.10.2014, 19:40 15
Цитата Сообщение от Nevermind_qqq Посмотреть сообщение
исполнителем по факту был человек
Тем не менее это не противоречит определению алгоритма. И после того как я его записал на ЯП, оттранслировал, его уже может исполнить машина. Да и любой алгоритм придумывает (или находит в Гугле) человек. Хотя, возможно, последняя фраза не точна. Ведь навярняка уже есть роботы, которые могут найти в Гугле нужный алгоритм (который изначально все-таки придумал человек)
Цитата Сообщение от ValeryS Посмотреть сообщение
вот здесь непонятно битовый поля? но как паковывать?
Где-то валяется у меня на чердаке код. Поскребу по сусекам, найду - выложу
0
ValeryS
Модератор
7271 / 5525 / 692
Регистрация: 14.02.2011
Сообщений: 18,714
22.10.2014, 19:50 16
Цитата Сообщение от Байт Посмотреть сообщение
Поскребу по сусекам, найду - выложу
давай интересно будет
нет я придумал что в байт пакуем нечетные числа, четные неинтересно
1 простое 0 нет
но только 15 могу впихать а не 30

Не по теме:


кстати загляни на эту тему В поисках логики
у меня словьев нехватает:(, может тебе как математику проще будет объяснить



Добавлено через 2 минуты
Цитата Сообщение от Nevermind_qqq Посмотреть сообщение
исполнителем по факту был человек(вы естественно) ,
а программу кто пишет?

и например таблица умножения, которую заучивают а не вычисляют сложением, можно ли сказать, что если я считаю 5х5=25 то исполнителем был человек который придумал эту таблицу?
0
Байт
Эксперт C
18523 / 12029 / 2507
Регистрация: 24.12.2010
Сообщений: 24,301
22.10.2014, 19:52 17
Цитата Сообщение от ValeryS Посмотреть сообщение
но только 15 могу впихать а не 30
Впихивать надо только те, которые дают от деления на 30 остатки 1, 7, 11, 13, 17, 19, 23, 29. А их ровно 8.
0
ValeryS
Модератор
7271 / 5525 / 692
Регистрация: 14.02.2011
Сообщений: 18,714
22.10.2014, 19:57 18
Цитата Сообщение от Байт Посмотреть сообщение
Впихивать надо только те, которые дают от деления на 30 остатки 1, 7, 11, 13, 17, 19, 23, 29. А их ровно 8.
а распределение у них равномерное?
честно говоря сейчас лень проверять
и куда делись простые 2 3 5 ???

Добавлено через 1 минуту
и потом выигрывая в памяти, не проигрываем ли мы в скорости(распаковка)???
0
Байт
Эксперт C
18523 / 12029 / 2507
Регистрация: 24.12.2010
Сообщений: 24,301
22.10.2014, 20:08 19
Цитата Сообщение от ValeryS Посмотреть сообщение
у меня словьев нехватает, может тебе как математику проще будет объяснить
ИМХО, там все правильно ты написал. А если кто не хочет слышать, так ему не объяснит ни Эйлер, ни Ландау, ни Перельман...

Добавлено через 4 минуты
Цитата Сообщение от ValeryS Посмотреть сообщение
а распределение у них равномерное?
Конечно, нет. Простых чисел чем дальше - тем меньше.
Цитата Сообщение от ValeryS Посмотреть сообщение
и куда делись простые 2 3 5 ???
Цитата Сообщение от Байт Посмотреть сообщение
Конечно, первую тридцатку приходится выводить вручную...
Это как у тебя - 2 и 3 отдельно вывел
Цитата Сообщение от ValeryS Посмотреть сообщение
и потом выигрывая в памяти, не проигрываем ли мы в скорости(распаковка)???
Не думаю. Ведь проверять приходится меньше чисел.
1
ValeryS
22.10.2014, 20:11     Поиск простых чисел
  #20

Не по теме:

Цитата Сообщение от Байт Посмотреть сообщение
Перельман..
это современный? к своему стыду не помню имени:(
или Яков?
хороший популяризатор, до сих пор книжки его почитываю:)
может простыми словами объяснить проблему

0
22.10.2014, 20:11
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
22.10.2014, 20:11
Привет! Вот еще темы с ответами:

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

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

Поиск простых чисел
to idetify if the given K is prime or not. Prime number is the number that can...


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

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

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2018, vBulletin Solutions, Inc.
Рейтинг@Mail.ru