Форум программистов, компьютерный форум, киберфорум
Наши страницы

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
 
turbokolor
0 / 0 / 0
Регистрация: 23.08.2015
Сообщений: 12
#1

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

24.08.2015, 13:44. Просмотров 549. Ответов 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++):

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

Поиск простых чисел - C++
Знаю, что тема избитая, но решил написать алгоритм поиска простых чисел. int j,i,k /*количество простых*/ ,nech,prime; ...

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

Поиск простых чисел - C++
to idetify if the given K is prime or not. Prime number is the number that can be divided by 1 and by itself ONLY. If given number is...

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

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

24
_Ivana
3185 / 1801 / 153
Регистрация: 01.03.2013
Сообщений: 5,030
Записей в блоге: 3
24.08.2015, 13:49 #2
Лучший ответ Сообщение было отмечено автором темы, экспертом или модератором как ответ
Потому что
C++
1
2
else
            return true;
ЗЫ проверять до a это моветон. Не использовать гипотезу Бертрана или хотя бы решето Эратосфена на худой конец - также моветон, но следующего порядка.
1
turbokolor
0 / 0 / 0
Регистрация: 23.08.2015
Сообщений: 12
24.08.2015, 14:02  [ТС] #3
Спасибо, буду учить вышеуказанные алгоритмы
0
_Ivana
3185 / 1801 / 153
Регистрация: 01.03.2013
Сообщений: 5,030
Записей в блоге: 3
24.08.2015, 14:04 #4
ЗЗЫ да, еще моветон минус первого порядка - проверять на простоту четные числа
C++
1
2
3
for (int i = 1; i < 100; i++)
    {
        switch (prost(i))
0
ValeryS
Модератор
6705 / 5114 / 482
Регистрация: 14.02.2011
Сообщений: 17,182
24.08.2015, 14:04 #5
Лучший ответ Сообщение было отмечено автором темы, экспертом или модератором как ответ
почитай вот эту тему
Быстрая проверка натурального числа на простоту
1
SerVal
23 / 23 / 2
Регистрация: 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
Модератор
6705 / 5114 / 482
Регистрация: 14.02.2011
Сообщений: 17,182
24.08.2015, 21:13 #7
is_prime это проверка на простоту?
0
SerVal
23 / 23 / 2
Регистрация: 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
Модератор
6705 / 5114 / 482
Регистрация: 14.02.2011
Сообщений: 17,182
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
Эксперт С++
4887 / 3022 / 370
Регистрация: 10.11.2010
Сообщений: 11,080
Записей в блоге: 10
Завершенные тесты: 1
24.08.2015, 21:47 #10
С таким алгоритмом у меня первые восемь натуральных чисел являются простыми.
0
SerVal
23 / 23 / 2
Регистрация: 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
Эксперт С++
4887 / 3022 / 370
Регистрация: 10.11.2010
Сообщений: 11,080
Записей в блоге: 10
Завершенные тесты: 1
24.08.2015, 21:56 #12
А 1 по определению простое?
0
_Ivana
3185 / 1801 / 153
Регистрация: 01.03.2013
Сообщений: 5,030
Записей в блоге: 3
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 / 2
Регистрация: 16.04.2015
Сообщений: 208
24.08.2015, 22:04 #14
Цитата Сообщение от castaway Посмотреть сообщение
А 1 по определению простое?
1 по определению, не является простым.
0
ValeryS
Модератор
6705 / 5114 / 482
Регистрация: 14.02.2011
Сообщений: 17,182
24.08.2015, 22:07 #15
Цитата Сообщение от castaway Посмотреть сообщение
А 1 по определению простое?
а никакое
сложным его не назвать,ибо ни на что не делится
и под простое не попадает, делится на единицу и на себя
во всех определениях читал, 1 не является простым, и баста
0
24.08.2015, 22:07
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
24.08.2015, 22:07
Привет! Вот еще темы с ответами:

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

Поиск простых чисел в массиве - C++
Здесь, на форуме для начинающих, была задачка, в которой в матрице A(m,n), состоящей из целых чисел, нужно было найти простые числа (те,...

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

Конкурс(поиск простых чисел) - C++
Я тут подумал, посмотрел по теме Hello world'a как всем нравится находить изощренные способы.Так вот - задание на засыпку: написать...


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

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

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