Форум программистов, компьютерный форум CyberForum.ru

Определить, содержит ли последовательность хотя бы одно простое число - C++

Восстановить пароль Регистрация
 
Анастасия_Я
0 / 0 / 0
Регистрация: 24.09.2010
Сообщений: 6
24.09.2010, 15:08     Определить, содержит ли последовательность хотя бы одно простое число #1
Вводится последовательность из N целых положительных элемен-тов. Определить, содержит ли последовательность хотя бы одно простое чис¬ло. Для определения простого числа создать функцию.
Подскажите как делать,пожалуйста.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
24.09.2010, 15:08     Определить, содержит ли последовательность хотя бы одно простое число
Посмотрите здесь:

Определить, содержит ли последовательность хотя бы одно совершенное число C++
Определить содержит ли последовательность хотя бы два рядом стоящих положительных числа C++
C++ содержит ли последовательность хотя бы два соседних числа с одинаковыми знаками.
C++ Дан массив из N целых чисел. Выяснить имеется ли в массиве хотя бы одно нечетное отрицательное число и определить его местонахождение в массиве
Определить, есть ли в строке(string) хотя бы одно число и определить есть ли в тексте хотя бы два числа. C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
PointsEqual
ниначмуроФ
 Аватар для PointsEqual
832 / 516 / 33
Регистрация: 12.10.2009
Сообщений: 1,915
24.09.2010, 15:21     Определить, содержит ли последовательность хотя бы одно простое число #2
http://ru.wikipedia.org/wiki/Простое_число
gooseim
Эксперт C++
500 / 404 / 35
Регистрация: 23.09.2010
Сообщений: 1,139
24.09.2010, 15:26     Определить, содержит ли последовательность хотя бы одно простое число #3
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <iostream>
#include <cmath>
 
bool is_simple(int n)
{
    return (int)std::pow(3.0, (n-1)) % n == 1;
}
 
int main(int argc, char* argv[])
{
    while(1)
    {
        int val;
        std::cin>>val;
        if(is_simple(val))
        {
            std::cout<<"simple"<<std::endl;
            break;
        }
    }
    std::system("pause");
    return 0;
}
Добавлено через 1 минуту
Если сначала ввести последовательность, потом проверить, то вот:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <iostream>
#include <iterator>
#include <algorithm>
#include <list>
#include <cmath>
 
bool is_simple(int n)
{
    return (int)std::pow(3.0, (n-1)) % n == 1;
}
 
int main(int argc, char* argv[])
{
    std::list<int> seq;
    std::copy(std::istream_iterator<int>(std::cin), std::istream_iterator<int>(), std::back_inserter(seq));
    if(std::find_if(seq.begin(), seq.end(), is_simple)!=seq.end())
        std::cout<<"yes"<<std::endl;
    else
        std::cout<<"no"<<std::endl;
    std::system("pause");
    return 0;
}
Чтобы закончить ввод, жми в виндах Ctrl+Z
dihlofos
Бродяга
 Аватар для dihlofos
302 / 256 / 17
Регистрация: 27.08.2010
Сообщений: 553
24.09.2010, 15:28     Определить, содержит ли последовательность хотя бы одно простое число #4
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
#include <iostream.h>
#include <math.h>
 
// Функция
bool simple(int x)
{
    int i;
    for(i=2;i<=sqrt(x);i++)
        if(x%i==0)
           return 0;
    return 1;
}
 
int main()
{
    int n,i;
    cout<<"Vvedite n ";
    cin>>n;
 
    int *a=new int[n];
 
    srand(time(NULL));
 
    for (i = 0; i < n; i++)
    {
        a[i]=rand()%100;
        cout<<a[i]<<' ';
    }
 
        for (i = 0; i < n; i++)
    {
        if (simple(a[i]))
        {
            cout<<"\nNajdeno prostoe chislo: "<<a[i];
            break;
        }
    }
 
 
    delete []a;
    cout<<endl;
    system("pause");
    return 0;
}
easybudda
Модератор
Эксперт С++
 Аватар для easybudda
9373 / 5423 / 914
Регистрация: 25.07.2009
Сообщений: 10,423
24.09.2010, 15:34     Определить, содержит ли последовательность хотя бы одно простое число #5
Цитата Сообщение от gooseim Посмотреть сообщение
C++
1
return (int)std::pow(3.0, (n-1)) % n == 1;
А можно с этого момента поподробнее? Какая-то хитрая формула для определения простых чисел... Это откуда такое?
gooseim
Эксперт C++
500 / 404 / 35
Регистрация: 23.09.2010
Сообщений: 1,139
24.09.2010, 15:36     Определить, содержит ли последовательность хотя бы одно простое число #6
easybudda, что-то как-то связанное с Кнутом. Я когда-то давно нашел ее на каком-то форуме. Она работает процентов на 95. Чтобы еще большей точности добиться, можно проверить еще по одному основанию. Тогда будет стремиться к 100%.
Dzhej-Dzhej
Заблокирован
24.09.2010, 16:13     Определить, содержит ли последовательность хотя бы одно простое число #7
Цитата Сообщение от gooseim Посмотреть сообщение
pow(3.0, (n-1)) % n == 1
это неправильная формула до 1000 выдает
2 5 7 11 13 17 19 23 29 31 47
Добавлено через 4 минуты
хотя может это переполнение типа ulong
до 50 пропущены: 3 37 41 43, а это уже не 95%
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
24.09.2010, 20:21     Определить, содержит ли последовательность хотя бы одно простое число
Еще ссылки по теме:

C++ Определить, есть ли в последовательности хотя бы одно число, кратное 7
C++ Поменять местами соответственные элементы массива, если хотя бы одно из них простое число
Определить содержит ли последовательность хотя бы три положительных нечетных числа C++

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

Или воспользуйтесь поиском по форуму:
gooseim
Эксперт C++
500 / 404 / 35
Регистрация: 23.09.2010
Сообщений: 1,139
24.09.2010, 20:21     Определить, содержит ли последовательность хотя бы одно простое число #8
Dzhej-Dzhej, это из-за overflow. Я вечером дам безошибочный алгоритм. Надо просто по-другому посчитать степень по модулю.

Добавлено через 2 часа 37 минут
Вот код, который корректно ищет простые числа в диапазоне от 3 до 1000 (немного жутковато, но зато быстро):
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
#include <iostream>
 
int log2(unsigned long x)
{
    if (x==0) return -1;
    int n=0;
    if (x<=0x0000FFFFul) {n+=16;x<<=16;}
    if (x<=0x00FFFFFFul) {n+=8 ;x<<=8;}
    if (x<=0x0FFFFFFFul) {n+=4 ;x<<=4;}
    if (x<=0x3FFFFFFFul) {n+=2 ;x<<=2;}
    if (x<=0x7FFFFFFFul) {n+=1 ;}
    return 31-n;
}
 
int bit_length(int x)
{
    return log2(x)+1;
}
 
 
bool get_bit(int val, int index)
{
    unsigned n=(1<<index);
    return (bool)(((unsigned)(val))&n);
}
 
 
int powmod(int x, int y, int mod)
{
    int *a=new int[bit_length(y)];
    a[0]=x%mod;
    for(int i=1;i<bit_length(y);i++)
        a[i]=(a[i-1]*a[i-1])%mod;
    int res=1;
    for(int i=bit_length(y)-1;i>=0;i--)
        if(get_bit(y, i))
            res=(res*a[i])%mod;
    delete[] a;
    return res;
}
 
 
bool is_simple(int n)
{
    if(n==3) return true;
    return powmod(3, (n-1), n) == 1;
}
 
int main(int argc, char* argv[])
{
    for(size_t i=3;i<1000;i++)
    {
        if(is_simple(i))
            std::cout<<i<<std::endl;
    }
    std::system("pause");
    return 0;
}
Yandex
Объявления
24.09.2010, 20:21     Определить, содержит ли последовательность хотя бы одно простое число
Ответ Создать тему
Опции темы

Текущее время: 00:20. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru