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

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

Войти
Регистрация
Восстановить пароль
 
Анастасия_Я
0 / 0 / 0
Регистрация: 24.09.2010
Сообщений: 6
#1

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

24.09.2010, 15:08. Просмотров 827. Ответов 7
Метки нет (Все метки)

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

Определить, содержит ли последовательность хотя бы одно совершенное число - C++
Вводится последовательность целых чисел, 0 - конец последовательности. Определить, содержит ли последовательность хотя бы одно совер¬шенное...

Поменять местами соответственные элементы массива, если хотя бы одно из них простое число - C++
#include <iostream> #include <math.h> using namespace std; int main () { int a; int b;

Вводится последовательность целых чисел,0 –конец последовательности. Определить, содержит ли последовательность хотя бы три отрицательных четных числа - C++
Составить алгоритм решения задачи и написать программу на языке С++. В алгоритме и программе массивов не использовать. ...

Определить, есть ли в строке(string) хотя бы одно число и определить есть ли в тексте хотя бы два числа. - C++
Помогите пожалуйста с заданиями. Определить, есть ли в строке(string) хотя бы одно число. Определить есть ли в тексте хотя бы два числа.

Определить, содержит ли последовательность хотя бы два числа, кратных 3, 5 и 7 - C++
ЗАДАЧА 1.Вводится последовательность целых чисел, 0 – конец последователь- ности. Содержит последовательность хотя бы два числа, кратных...

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

7
PointsEqual
ниначмуроФ
836 / 520 / 33
Регистрация: 12.10.2009
Сообщений: 1,915
24.09.2010, 15:21 #2
http://ru.wikipedia.org/wiki/Простое_число
0
gooseim
Эксперт С++
508 / 412 / 37
Регистрация: 23.09.2010
Сообщений: 1,159
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
0
dihlofos
Бродяга
303 / 257 / 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;
}
0
easybudda
Модератор
Эксперт CЭксперт С++
9695 / 5645 / 963
Регистрация: 25.07.2009
Сообщений: 10,850
24.09.2010, 15:34 #5
Цитата Сообщение от gooseim Посмотреть сообщение
C++
1
return (int)std::pow(3.0, (n-1)) % n == 1;
А можно с этого момента поподробнее? Какая-то хитрая формула для определения простых чисел... Это откуда такое?
0
gooseim
Эксперт С++
508 / 412 / 37
Регистрация: 23.09.2010
Сообщений: 1,159
24.09.2010, 15:36 #6
easybudda, что-то как-то связанное с Кнутом. Я когда-то давно нашел ее на каком-то форуме. Она работает процентов на 95. Чтобы еще большей точности добиться, можно проверить еще по одному основанию. Тогда будет стремиться к 100%.
1
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%
0
gooseim
Эксперт С++
508 / 412 / 37
Регистрация: 23.09.2010
Сообщений: 1,159
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;
}
0
24.09.2010, 20:21
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
24.09.2010, 20:21
Привет! Вот еще темы с ответами:

Определить содержит ли последовательность хотя бы два рядом стоящих положительных числа - C++
Помогите пожалуйста решить. Буду очень признательна. Вводится последовательность целых чисел, 0 – конец последователь- ности....

Определить, есть ли в последовательности хотя бы одно число, кратное 7 - C++
не лезет в голову программа,хоть убейте,остальное всё сделал,осталась одна,помогите,будь добры. Дана непустая последовательность целых...

Выяснить есть ли в массиве хотя бы одно нечетное отрицательное число и определить его местонахождение - C++
Выяснить есть ли в массиве хотя бы одно нечетное отрицательное число и определить его местонахождение. я так понимаю что это индекс у...

Дан массив из N целых чисел. Выяснить имеется ли в массиве хотя бы одно нечетное отрицательное число и определить его местонахождение в массиве - C++
1. Дан массив из N целых чисел. Выяснить имеется ли в массиве хотя бы одно нечетное отрицательное число и определить его местонахождение в...


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

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

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