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

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

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 12, средняя оценка - 4.75
Sens0
15 / 2 / 0
Регистрация: 06.12.2009
Сообщений: 27
#1

Простые числа - C++

06.12.2009, 15:30. Просмотров 1468. Ответов 5
Метки нет (Все метки)

Привет всем! Ребята, помогите написать программу:
1). Найти все простые числа, меньше заданного "n"
2). Найти все простые делители предложенного числа
3). Найти все простые числа из заданного промежутка
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
06.12.2009, 15:30     Простые числа
Посмотрите здесь:

Простые числа C++
C++ Простые числа
C++ Простые числа
Простые числа C++
Простые числа C++
Простые числа. C++
C++ Простые числа
Простые числа C++
Числа Фибоначчи, простые числа и делители C++
C++ Вывести все простые числа до заданного числа
Найти сверхпростые числа: простые числа, номера которых являются простыми числами. C++
Найти простые числа с суммой цифр меньше заданного числа C++

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

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
odip
Эксперт С++
7155 / 3295 / 59
Регистрация: 17.06.2009
Сообщений: 14,164
07.12.2009, 08:06     Простые числа #2
В форуме много раз решали подобные задачи.
В том числе поиск простых чисел есть в FAQ:
http://www.cyberforum.ru/cpp-beginne...tml#post243387
Sens0
15 / 2 / 0
Регистрация: 06.12.2009
Сообщений: 27
07.12.2009, 10:52  [ТС]     Простые числа #3
Я в ФАКе не нашел простых чисел, там только сортировка...
Vladimir.
155 / 155 / 10
Регистрация: 24.11.2009
Сообщений: 375
07.12.2009, 11:42     Простые числа #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
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
/*
немного рассуждений:
Пусть P_1,P_2, P_3, P_4,..,P_k-1, P_k - простые числа, причем P_i<P_i+1 при любых
 
i=1,2,3,....k-1.
любое число можно представить ввиде
n = {(P_1)^S_1}*{(P_2)^S_2}*{(P_3)^S_3}*{(p_4)^S_4}*.. .*{(P_k-1)^S_k-1}*{(P_k)^S_k} 
//^-возведение в степень 2^3=8;
где S_i = 0,1,2,3... кратность простого множителя.
оценим максимальный множитель:
так как P_i<P_i+1 оценим для P_k.
{(P_k)^S_k} = n/[{(P_1)^S_1}*{(P_2)^S_2}*{(P_3)^S_3}*...*{(P_k-1)^S_k-1}]
 
пусть сложилась ситуация, такая что
 
[{(P_1)^S_1}*{(P_2)^S_2}*{(P_3)^S_3}*{(p_4)^S_4}*.. .*{(P_k-1)^S_k-1}] = 1
то есть S_i = 0 для i = 1,2,3,4,.., k-2,k-1;
 
тогда {(P_k)^S_k} = n (а обычно меньше т.к. знаменатель обычно не равен 1), т.е.
{(P_k)^S_k} <= n
 
вариант 1: S_k = 0, невозможен при правильном k (доказывать не будем, впринципе очевидно.)
вариант 2: S_k = 1, n = P_k; n простое.
вариант 3: S_k = 2, p_k*p_k <= n т.е. p_k<= (n^0.5)
вариант 4: S_k = 3, p_k*p_k*p_k<=n p_k< (n^0.5)
 
таким образом проверять простые делители следует от 2 до значения квадратного корня из n 
включительно, а так же убедиться в том что n не являеться простым. (Последнее верно если 
нашелся хотя бы один делитель для n в указанном промежутке обязательно найдеться простой 
делитель;  если же нет, то n простое.)
 
#include<iostream.h>
 
/**********************************************************
cancellation() Выясняет являеться ли divisor делителем для 
number, если да, то находит кратность делителя и возвращает 
зачение (number/(divisor^S)) 
**********************************************************************/
 
 
/************************************************************************
Ведём перебор возможных делителей для number (он будет 
лежать в промежутке до корня из number включительно, если 
number - сложное, то возможное 
значение передаем функции cancellation(); перебор возможных 
делителей оптимизирован исключением чисел вида 2k, где 
k=1,2,3,4,5,6,...; по предложению cheburator'а возможно 
исключение чисел вида 3k, 5k  и т.п.
делителей оптимизирован исключением чисел вида 2k, где 
k=1,2,3,4,5,6,...; возможно 
исключение чисел вида 3k, 5k  и т.п.
*********************************************************************/
#include<iostream.h>
int cancellation(int divisor,int number);
 
int main()
{
 int n,number;
 cout<<"\nInput number..."<<endl; 
 cin>>n;
 cout<<"\nSolve..."<<endl;
 
 number=n;
 number=cancellation(2,number);
 
 int k=3;
 while (k*k <= number)
 {
   psi=cancellation(k,psi);
   k+=2;
 }
 
  cout<<number;
  cout<<"\nDone..."<<endl;
 
  return (0);
}
 
int cancellation (int divisor,int number)
{
 if ((number%divisor)==0) cout<<divisor<<"\t";
 while((number%divisor)==0) number/=divisor;
 return (number);
}
valeriikozlov
Эксперт C++
4663 / 2489 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
07.12.2009, 11:56     Простые числа #5
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
#include <iostream.h>
#include <windows.h>
#include<conio.h>
bool prost(int n)
{
    bool fl=true;
    for(int i=2; fl && i<n; i++)
        if(n%i==0)
            fl=false;
    return fl;
}
 
int main()
{
    int i, n, i_start, i_end;
    SetConsoleCP(1251);
    SetConsoleOutputCP(1251);
    cout<<"Ââåäèòå ÷èñëî äëÿ Г*Г*õîæäåГ*ГЁГї ГўГ±ГҐГµ ïðîñòûõ Г·ГЁГ±ГҐГ«, ìåГ*ГјГёГҐ ýòîãî Г·ГЁГ±Г«Г*: "<< endl;
    cin>>n;
    cout<<"Âñå ïðîñòûå Г·ГЁГ±Г«Г* ìåГ*ГјГёГЁГҐ Г·ГҐГ¬ "<<n<<":"<<endl;
    for(i=2; i<n; i++)
        if(prost(i))
            cout<<i<<" ";
    cout<<endl;
    cout<<"Ââåäèòå ÷èñëî äëÿ Г*Г*õîæäåГ*ГЁГї ГўГ±ГҐГµ ïðîñòûõ äåëèòåëåé ýòîãî Г·ГЁГ±Г«Г*: "<< endl;
    cin>>n;
    cout<<"Âñå ïðîñòûå äåëèòåëè "<<n<<":"<<endl;
    for(i=2; i<=n; i++)
        if(n%i==0 && prost(i))
            cout<<i<<" ";
    cout<<endl;
    cout<<"Ââåäèòå Г*Г*Г·Г*ëî ïðîìåæóòêГ*: "<< endl;
    cin>>i_start;
    cout<<"Ââåäèòå ГЄГ®Г*ГҐГ¶ ïðîìåæóòêГ*: "<< endl;
    cin>>i_end;
    cout<<"Âñå ïðîñòûå Г·ГЁГ±Г«Г* ГЁГ§ ïðîìåæóòêГ* îò "<<i_start<<" äî "<<i_end<<endl;
    for(i=i_start; i<=i_end; i++)
        if(prost(i))
            cout<<i<<" ";
    cout<<endl;
    getch();
    return 0;
}
Sens0
15 / 2 / 0
Регистрация: 06.12.2009
Сообщений: 27
07.12.2009, 22:34  [ТС]     Простые числа #6
Cпасибо всем за помощь
Yandex
Объявления
07.12.2009, 22:34     Простые числа
Ответ Создать тему
Опции темы

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