Форум программистов, компьютерный форум, киберфорум
Наши страницы
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
 
turbokolor
0 / 0 / 0
Регистрация: 23.08.2015
Сообщений: 12
#1

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

24.08.2015, 13:44. Просмотров 602. Ответов 24
Метки нет (Все метки)

Почему мне возвращает просто непарные числа? в чем загвоздка
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
33
34
35
#include <iostream>
bool prost(int);
using namespace std;
int main()
{
    //int a;
    //cout << "vashe czislo" << endl;
    //cin >> a;
    for (int i = 1; i < 100; i++)
    {
        switch (prost(i))
        {
        case true: cout <<"chislo "<<i<< " prost" << endl;
            break;
        default:
            break;
            //case false: cout << "ne prost"<<endl;
            //break;
        }
    }
    system("pause");
    return 0;
    }
bool prost(int a)
{
    if (a<=2 && a>0)
        return true;
    for (int i = 2; i < a; i++)
    {
        if (a%i == 0 )
            return false;
        else
            return true;
    }
}
0
Миниатюры
Поиск простых чисел  
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
24.08.2015, 13:44
Я подобрал для вас темы с готовыми решениями и ответами на вопрос Поиск простых чисел (C++):

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

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

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

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

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

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

24
_Ivana
3233 / 1861 / 235
Регистрация: 01.03.2013
Сообщений: 5,091
Записей в блоге: 5
24.08.2015, 13:49 #2
Лучший ответ Сообщение было отмечено turbokolor как решение

Решение

Потому что
C++
1
2
else
            return true;
ЗЫ проверять до a это моветон. Не использовать гипотезу Бертрана или хотя бы решето Эратосфена на худой конец - также моветон, но следующего порядка.
1
turbokolor
0 / 0 / 0
Регистрация: 23.08.2015
Сообщений: 12
24.08.2015, 14:02  [ТС] #3
Спасибо, буду учить вышеуказанные алгоритмы
0
_Ivana
3233 / 1861 / 235
Регистрация: 01.03.2013
Сообщений: 5,091
Записей в блоге: 5
24.08.2015, 14:04 #4
ЗЗЫ да, еще моветон минус первого порядка - проверять на простоту четные числа
C++
1
2
3
for (int i = 1; i < 100; i++)
    {
        switch (prost(i))
0
ValeryS
Модератор
7131 / 5399 / 669
Регистрация: 14.02.2011
Сообщений: 18,221
24.08.2015, 14:04 #5
Лучший ответ Сообщение было отмечено turbokolor как решение

Решение

почитай вот эту тему
http://www.cyberforum.ru/cpp-beginners/thread660361.html
1
SerVal
23 / 23 / 8
Регистрация: 16.04.2015
Сообщений: 208
24.08.2015, 20:37 #6
Как-то так:
Кликните здесь для просмотра всего текста

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
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
bool is_prime(unsigned long long x)
{
    for (unsigned long long i = 3; true; i += 2)
    {
        unsigned long long q = x / i;
        if (q < i)
            return true;
        if (x == q * i)
            return false;
    }
    return true;
}
 
unsigned long long next_prime(unsigned long long x)
{
    if (x <= 2)
        return 2;
    unsigned long long next_prime = x + 1;
    if (!(next_prime & 1))
        next_prime++;
    for (; !is_prime(next_prime); next_prime += 2)
        ;
    return next_prime;
}
 
 
static void GetAllPrimesSmallerThanOrEqualTo(unsigned long long n, std::vector<unsigned long long>& output)
{
    std::vector<int> theSieve;
    theSieve.resize(n + 1);
 
    for (unsigned long long i = 0; i<n + 1; i++)
        theSieve[i] = 1;
    output.resize(0);
    output.reserve(n / 2);
 
    for (unsigned long long i = 2; i <= n; i++)
        if (theSieve[i] != 0)
        {
            output.push_back(i);
            for (unsigned long long j = i; j <= n; j += i)
                theSieve[j] = 0;
        }
}
 
int main(int argc, char *argv[])
{
    setlocale(LC_CTYPE, "russian");
 
    unsigned long long upper_bound = 100000;  // диапазон 0...100000 
    std::vector<unsigned long long>myPrimes;
    
    double total_time = (double)clock() / CLOCKS_PER_SEC;
    GetAllPrimesSmallerThanOrEqualTo(upper_bound, myPrimes);
 
    std::cout << std::endl << " Простые числа в диапазоне 0 ... " << upper_bound << std::endl;
    std::cout << " количество :  " << myPrimes.size() << std::endl;
 
    std::cout << " первое     :  " << myPrimes[0] << std::endl;
    std::cout << " последнее  :  " << myPrimes[myPrimes.size()-1] << std::endl;
 
    std::cout << std::endl << " time : " << (double)clock() / CLOCKS_PER_SEC - total_time << " sec." << std::endl << std::endl;
}


C++
1
2
3
4
5
6
7
Output:
 Простые числа в диапазоне 0 ... 100000
 количество :  9592
 первое     :  2
 последнее  :  99991
 
 time : 0.014 sec.
0
ValeryS
Модератор
7131 / 5399 / 669
Регистрация: 14.02.2011
Сообщений: 18,221
24.08.2015, 21:13 #7
is_prime это проверка на простоту?
0
SerVal
23 / 23 / 8
Регистрация: 16.04.2015
Сообщений: 208
24.08.2015, 21:17 #8
Цитата Сообщение от ValeryS Посмотреть сообщение
is_prime это проверка на простоту?
Ага.

.. заодно померял для диапазона 0 .. 100 миллионов.

C++
1
2
3
4
5
6
 Простые числа в диапазоне 0 ... 100000000
 количество :  5761455
 первое     :  2
 последнее  :  99999989
 
 time : 6.38 sec.
0
ValeryS
Модератор
7131 / 5399 / 669
Регистрация: 14.02.2011
Сообщений: 18,221
24.08.2015, 21:28 #9
Цитата Сообщение от SerVal Посмотреть сообщение
Ага.
проверим для числа 6 (или 4)

Цитата Сообщение от SerVal Посмотреть сообщение
C++
1
2
3
4
5
6
7
bool is_prime(unsigned long long x)
{
    for (unsigned long long i = 3; true; i += 2)
    {
        unsigned long long q = x / i;
        if (q < i)
            return true
;
q=4/3=1
1<3
опаньки простое
q=6/3=2
2<3
опять же
или я чего не понял
1
castaway
Эксперт С++
4926 / 3033 / 453
Регистрация: 10.11.2010
Сообщений: 11,089
Записей в блоге: 10
Завершенные тесты: 1
24.08.2015, 21:47 #10
С таким алгоритмом у меня первые восемь натуральных чисел являются простыми.
0
SerVal
23 / 23 / 8
Регистрация: 16.04.2015
Сообщений: 208
24.08.2015, 21:51 #11
Маху дал.
Похоже, надо так.

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
bool is_prime(unsigned long long x)
{
    if (x == 2) return true;     // по определению
    if (!(x & 1)) return false;   // чётное
 
    for (unsigned long long i = 3; true; i += 2)
    {
        unsigned long long q = x / i;
        if (q < i)
            return true;
        if (x == q * i)
            return false;
    }
    return true;
}
0
castaway
Эксперт С++
4926 / 3033 / 453
Регистрация: 10.11.2010
Сообщений: 11,089
Записей в блоге: 10
Завершенные тесты: 1
24.08.2015, 21:56 #12
А 1 по определению простое?
0
_Ivana
3233 / 1861 / 235
Регистрация: 01.03.2013
Сообщений: 5,091
Записей в блоге: 5
24.08.2015, 22:03 #13
Haskell
1
2
3
4
5
primes :: [Int]
primes = 2 : filter isprime [3,5..100000] where
    isprime n = all ((/=0).(rem n)) $ takeWhile ((<=n).(^2)) primes
 
main = print . length $ primes
Успешно time: 0.04 memory: 4644 signal:0
9592
https://ideone.com/j5TVv7

Всего в 3 раза медленнее представленного выше сишного кота (и то неизвестно сколько он будет считать в варианте с исправленной ошибкой), зато по количеству строк и ясности кода имхо выбор очевиден
0
SerVal
23 / 23 / 8
Регистрация: 16.04.2015
Сообщений: 208
24.08.2015, 22:04 #14
Цитата Сообщение от castaway Посмотреть сообщение
А 1 по определению простое?
1 по определению, не является простым.
0
ValeryS
Модератор
7131 / 5399 / 669
Регистрация: 14.02.2011
Сообщений: 18,221
24.08.2015, 22:07 #15
Цитата Сообщение от castaway Посмотреть сообщение
А 1 по определению простое?
а никакое
сложным его не назвать,ибо ни на что не делится
и под простое не попадает, делится на единицу и на себя
во всех определениях читал, 1 не является простым, и баста
0
castaway
Эксперт С++
4926 / 3033 / 453
Регистрация: 10.11.2010
Сообщений: 11,089
Записей в блоге: 10
Завершенные тесты: 1
24.08.2015, 22:07 #16
SerVal, я тоже так думаю. Просто вариант в 11-м сообщении думает по другому.
ValeryS, я намекал на маленькое упущение в последнем алгоритме)
0
SerVal
23 / 23 / 8
Регистрация: 16.04.2015
Сообщений: 208
24.08.2015, 22:08 #17
Цитата Сообщение от _Ivana Посмотреть сообщение
и то неизвестно сколько он будет считать в варианте с исправленной ошибкой
C++
1
2
3
4
5
6
Простые числа в диапазоне 0 ... 100000000
 количество :  5761455
 первое     :  2
 последнее  :  99999989
 
 time : 6.416 sec.
*кстати, для приведённого мной начального кода, в функции is_prime(x) нет ошибки, поскольку не она выдаёт окончательный результат. Результаты в векторе - правильные.
0
_Ivana
3233 / 1861 / 235
Регистрация: 01.03.2013
Сообщений: 5,091
Записей в блоге: 5
24.08.2015, 22:12 #18
Ideone больше 5 секунд не дает думать, поэтому сравнение только на малых временах.

ЗЫ не обязательно требовать совершенства от isprime, если она будет вызываться только на нечетных числах > 1 - она так избежит лишних проверок и может прибавить в скорости, а с четными аргументами и с 1 ее никто в здравом уме вызывать не будет - имхо это нормальная практика.
0
ValeryS
Модератор
7131 / 5399 / 669
Регистрация: 14.02.2011
Сообщений: 18,221
24.08.2015, 22:18 #19
Цитата Сообщение от castaway Посмотреть сообщение
ValeryS, я намекал на маленькое упущение в последнем алгоритме)
да я просто тему развил
потрепаться захотелось

Добавлено через 1 минуту
Цитата Сообщение от SerVal Посмотреть сообщение
стати, для приведённого мной начального кода, в функции is_prime(x) нет ошибки,
ошибка то есть
просто ты данные отсортировал, отбросил четные,вот она и замаскировалась

Добавлено через 2 минуты
Цитата Сообщение от _Ivana Посмотреть сообщение
а с четными аргументами и с 1 ее никто в здравом уме вызывать не будет - имхо это нормальная практика.
а у компа нет "здравого ума", вот пришли к нему куча данных, и пускай найдет простое
значит перед функцией нужно проверять на четность, а зачем, не проще в функции это сделать?
0
castaway
Эксперт С++
4926 / 3033 / 453
Регистрация: 10.11.2010
Сообщений: 11,089
Записей в блоге: 10
Завершенные тесты: 1
24.08.2015, 22:18 #20
Цитата Сообщение от ValeryS Посмотреть сообщение
ошибка то есть
Согласен. Имя функции не соответствует результату её выполнения.
0
24.08.2015, 22:18
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
24.08.2015, 22:18
Привет! Вот еще темы с решениями:

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

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

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

Поиск простых чисел на видеоадаптере
Использую CUDA. Для маленьких цифр всё замечательно. С цифрами побольше экран...


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

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

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