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

Эти простые числа... - C++

Восстановить пароль Регистрация
 
nikkka
Мат в 32 хода
 Аватар для nikkka
235 / 170 / 8
Регистрация: 10.09.2009
Сообщений: 1,096
02.01.2010, 14:08     Эти простые числа... #1
Программа должна определять является ли число n простым.
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
#include <iostream>
#include <conio.h>
#include <math.h>
#include <stdio.h>
 
 
using namespace std;
bool prime(int n)
{
        int k;
        k=(n/2)+1;
        if (n>2)
        {
        for (int i=2;i<=k;i++)
        {
            if (n % i == 0) {return false; goto 1;} 
        }
        }
        if (n=2) {return true; goto 1;} 
        if (n=1) {return false; goto 1;}
        if (n=0) {return false; goto 1;}
1:
}
 
main ()
{
int i;
cin >> i;
if (prime(i)) cout<<"Prime";
else cout<<"Not prime";
getch();
return 0;
}
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
02.01.2010, 14:08     Эти простые числа...
Посмотрите здесь:

Даны натуральные числа p и q. Получить все делители числа q, взаимно простые к p. C++
C++ Вывести все целые числа, расположенные между данными числами, включая сами эти числа, в порядке их возрастания
C++ Даны целые числа р и q. Получить все делители числа q, взаимно простые с р
Даны целые числа р и q. Получить все делители числа q, взаимно простые с р. C++
C++ Найти все трехзначные простые числа. Определить функцию позволяющую распознавать простые числа
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
FunDuck
688 / 379 / 4
Регистрация: 22.01.2009
Сообщений: 1,135
02.01.2010, 14:15     Эти простые числа... #2
зачем goto?

Добавлено через 4 минуты
И к тому же функция никогда (кроме случая, если n=2) не возвращает true.
fasked
Эксперт C++
 Аватар для fasked
4925 / 2505 / 180
Регистрация: 07.10.2009
Сообщений: 4,306
Записей в блоге: 1
02.01.2010, 14:30     Эти простые числа... #3
C++
1
2
3
4
5
6
7
8
9
10
bool is_prime(int n)
{
    if (n <= 1)
        return false;
 
    for (int j = 2; j * j <= n; j++)
         if (n % j == 0) return false;
 
    return true;
}
FunDuck
688 / 379 / 4
Регистрация: 22.01.2009
Сообщений: 1,135
02.01.2010, 14:50     Эти простые числа... #4
Цитата Сообщение от fasked Посмотреть сообщение
C++
1
2
3
4
5
6
7
8
9
10
bool is_prime(int n)
{
    if (n <= 1)
        return false;
 
    for (int j = 2; j * j <= n; j++)
         if (n % j == 0) return false;
 
    return true;
}
1. Зачем цикл?
2. Почему до j*j ?
fasked
Эксперт C++
 Аватар для fasked
4925 / 2505 / 180
Регистрация: 07.10.2009
Сообщений: 4,306
Записей в блоге: 1
02.01.2010, 14:59     Эти простые числа... #5
Цитата Сообщение от FunDuck Посмотреть сообщение
1. Зачем цикл?
2. Почему до j*j ?
Перебор делителей - алгоритм факторизации или тестирования простоты числа путем полного перебора всех возможных потенциальных делителей.

Обычно перебор делителей заключается в переборе всех целых чисел от 2 до квадратного корня из факторизуемого числа n и в вычислении остатка от деления n на каждое из этих чисел.
Ферма.
FunDuck
688 / 379 / 4
Регистрация: 22.01.2009
Сообщений: 1,135
02.01.2010, 15:20     Эти простые числа... #6
Мне кажется достаточно будет такого:
C++
1
2
3
bool is_prime(int n){
    return (n > 1 && (!(n % 2) && n == 2 || !(n % 3) && n == 3 || !(n % 5) && n == 5 || !(n % 7) && n == 7));
}
Перебор в некоторых случаях может занять много времени. Если не прав, поправьте

Добавлено через 10 минут
Точнее так:
C++
1
2
3
bool check(int n){
    return (n > 1 && (!(n % 2) && n == 2 || !(n % 3) && n == 3 || !(n % 5) && n == 5 || !(n % 7) && n == 7 || (n % 2 != 0 && n % 3 != 0 && n % 5 != 0 && n % 7 != 0)));
}
fasked
Эксперт C++
 Аватар для fasked
4925 / 2505 / 180
Регистрация: 07.10.2009
Сообщений: 4,306
Записей в блоге: 1
02.01.2010, 16:55     Эти простые числа... #7
я всего лишь переписал код nikka
outoftime
║XLR8║
 Аватар для outoftime
505 / 427 / 33
Регистрация: 25.07.2009
Сообщений: 2,297
02.01.2010, 18:34     Эти простые числа... #8
короче вот:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include <iostream>
using namespace std;
 
int gcd(int a, int b){return (a) ? (gcd(b%a,a)) : (b);}
 
int main()
{
    int n, b = 1;
    cin >> n;
    for (int i = 2; i*i <= n; ++i)
        if (gcd(n,i) != 1) b = 0;
    cout << ((b) ? ("yes") : ("no")) << endl;
    getchar();
    return 0;
}
Vladimir_Limaki
1 / 1 / 0
Регистрация: 02.01.2010
Сообщений: 39
02.01.2010, 23:16     Эти простые числа... #9
блин тут вообше все просто !!!!!!!!


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
#include <iostream>
#include <conio.h>
#include <math.h>
#include <stdio.h>
 
 
using namespace std;
bool is_prime(int n)
{
    if (n <= 1)
        return false;
 
    for (int j=2;j *j <= n; j++)
         if (n%j== 0) return false;
 
    return true;
}
 
void main ()
{locale::global(locale("rus"));
int i;
cout<<"введит начало интервала";
cin >> i;
cout<<"введите конец интервала"<<endl;
 
 
if (is_prime(i))
{cout<<"  простое  ";
}
 
else
{cout<<" не простое  ";
}
getch();
 
}
outoftime
║XLR8║
 Аватар для outoftime
505 / 427 / 33
Регистрация: 25.07.2009
Сообщений: 2,297
03.01.2010, 00:56     Эти простые числа... #10
Vladimir_Limaki, давай поспорим у кого проще
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
03.01.2010, 02:32     Эти простые числа...
Еще ссылки по теме:

C++ Пользователь ввел три целых числа, расположить эти числа в порядке убывания
C++ Массив A содержит только два одинаковых числа. Найти эти числа и указать их индексы ошибка
Даны натуральные числа p и q. Получить все делители числа q, взаимно простые к p C++

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

Или воспользуйтесь поиском по форуму:
Vladimir_Limaki
1 / 1 / 0
Регистрация: 02.01.2010
Сообщений: 39
03.01.2010, 02:32     Эти простые числа... #11
Добавлено через 18 минут
вот оно ты вводишь число и оно говорит простое или нет .!!!
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
#include <iostream>
#include <conio.h>
#include <math.h>
#include <stdio.h>
 
 
using namespace std;
bool is_prime(int n)
{
    if (n <= 1)
        return false;
 
    for (int j=2;j *j <= n; j++)
         if (n%j== 0) return false;
 
    return true;
}
 
void main ()
{locale::global(locale("rus"));
int i;
cout<<"введит начало интервала";
cin >> i;
cout<<"введите конец интервала"<<endl;
 
 
if (is_prime(i))
{cout<<"  простое  ";
}
 
else
{cout<<" не простое  ";
}
getch();
 
}
Yandex
Объявления
03.01.2010, 02:32     Эти простые числа...
Ответ Создать тему
Опции темы

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