Форум программистов, компьютерный форум, киберфорум
Наши страницы
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.76/38: Рейтинг темы: голосов - 38, средняя оценка - 4.76
wcl.AleX
0 / 0 / 0
Регистрация: 08.04.2011
Сообщений: 9
1

[Cи] Проверка чисел на простоту

08.04.2011, 10:34. Просмотров 7094. Ответов 19
Метки нет (Все метки)

Как в Си написать программу, которая проверяла бы вводимые числа на простоту вероятностными методами. Числа поряка 10^5000---10^20000 за приемлемое время?
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
08.04.2011, 10:34
Ответы с готовыми решениями:

Проверка чисел на простоту
сам код #include "stdafx.h" #include "iostream" #include "vector" using...

Проверка чисел на простоту и проверку на наличие общих цифр в записи
Помогите написать программу: Для каждого (n) из некоторого количества...

Проверка числа на простоту
Дано натуральное число n>1. Проверьте, является ли оно простым. Программа...

Проверка числа на простоту
Помогите написать программу которая проверяет простое число или нет.

Проверка числа на простоту
я реализовал вот так, но алгоритм очень долгий, мне надо проверять очень...

19
-comrade-
357 / 358 / 167
Регистрация: 11.06.2010
Сообщений: 703
11.04.2011, 16:34 2
wcl.AleX, такое подойдет:
C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <stdio.h>
#include <conio.h>
 
bool simple (int n) 
{
    if(n==1) return 0;
    for( int i=2;i<=n/2;i++) if(!(n%i)) return 0;
    return 1;
}
 
int main() 
{
      int n;
      printf("  N=");
      scanf("%d",&n);
      if(simple(n)) printf("  Yes");
      else printf("  No");
      getch();
      return 0;
};
0
wcl.AleX
0 / 0 / 0
Регистрация: 08.04.2011
Сообщений: 9
11.04.2011, 16:50  [ТС] 3
Код
alex@Alex:~$ gedit ./Prime.c
alex@Alex:~$ g++ ./Prime.c -lm -lgmp -o ./Prime
./Prime.c:2:19: error: conio.h: No such file or directory
./Prime.c:3: error: stray ‘\342’ in program
./Prime.c:3: error: stray ‘\225’ in program
./Prime.c:3: error: stray ‘\220’ in program
./Prime.c:6: error: stray ‘\342’ in program
./Prime.c:6: error: stray ‘\225’ in program
./Prime.c:6: error: stray ‘\220’ in program
./Prime.c:6: error: stray ‘\342’ in program
./Prime.c:6: error: stray ‘\225’ in program
./Prime.c:6: error: stray ‘\220’ in program
./Prime.c:7: error: stray ‘\342’ in program
./Prime.c:7: error: stray ‘\225’ in program
./Prime.c:7: error: stray ‘\220’ in program
./Prime.c:7: error: stray ‘\342’ in program
./Prime.c:7: error: stray ‘\225’ in program
./Prime.c:7: error: stray ‘\220’ in program
./Prime.c:8: error: stray ‘\342’ in program
./Prime.c:8: error: stray ‘\225’ in program
./Prime.c:8: error: stray ‘\220’ in program
./Prime.c:8: error: stray ‘\342’ in program
./Prime.c:8: error: stray ‘\225’ in program
./Prime.c:8: error: stray ‘\220’ in program
./Prime.c:10: error: stray ‘\342’ in program
./Prime.c:10: error: stray ‘\225’ in program
./Prime.c:10: error: stray ‘\220’ in program
./Prime.c:13: error: stray ‘\342’ in program
./Prime.c:13: error: stray ‘\225’ in program
./Prime.c:13: error: stray ‘\220’ in program
./Prime.c:13: error: stray ‘\342’ in program
./Prime.c:13: error: stray ‘\225’ in program
./Prime.c:13: error: stray ‘\220’ in program
./Prime.c:13: error: stray ‘\342’ in program
./Prime.c:13: error: stray ‘\225’ in program
./Prime.c:13: error: stray ‘\220’ in program
./Prime.c:14: error: stray ‘\342’ in program
./Prime.c:14: error: stray ‘\225’ in program
./Prime.c:14: error: stray ‘\220’ in program
./Prime.c:14: error: stray ‘\342’ in program
./Prime.c:14: error: stray ‘\225’ in program
./Prime.c:14: error: stray ‘\220’ in program
./Prime.c:14: error: stray ‘\342’ in program
./Prime.c:14: error: stray ‘\225’ in program
./Prime.c:14: error: stray ‘\220’ in program
./Prime.c:15: error: stray ‘\342’ in program
./Prime.c:15: error: stray ‘\225’ in program
./Prime.c:15: error: stray ‘\220’ in program
./Prime.c:15: error: stray ‘\342’ in program
./Prime.c:15: error: stray ‘\225’ in program
./Prime.c:15: error: stray ‘\220’ in program
./Prime.c:15: error: stray ‘\342’ in program
./Prime.c:15: error: stray ‘\225’ in program
./Prime.c:15: error: stray ‘\220’ in program
./Prime.c:16: error: stray ‘\342’ in program
./Prime.c:16: error: stray ‘\225’ in program
./Prime.c:16: error: stray ‘\220’ in program
./Prime.c:16: error: stray ‘\342’ in program
./Prime.c:16: error: stray ‘\225’ in program
./Prime.c:16: error: stray ‘\220’ in program
./Prime.c:16: error: stray ‘\342’ in program
./Prime.c:16: error: stray ‘\225’ in program
./Prime.c:16: error: stray ‘\220’ in program
./Prime.c:17: error: stray ‘\342’ in program
./Prime.c:17: error: stray ‘\225’ in program
./Prime.c:17: error: stray ‘\220’ in program
./Prime.c:17: error: stray ‘\342’ in program
./Prime.c:17: error: stray ‘\225’ in program
./Prime.c:17: error: stray ‘\220’ in program
./Prime.c:17: error: stray ‘\342’ in program
./Prime.c:17: error: stray ‘\225’ in program
./Prime.c:17: error: stray ‘\220’ in program
./Prime.c:18: error: stray ‘\342’ in program
./Prime.c:18: error: stray ‘\225’ in program
./Prime.c:18: error: stray ‘\220’ in program
./Prime.c:18: error: stray ‘\342’ in program
./Prime.c:18: error: stray ‘\225’ in program
./Prime.c:18: error: stray ‘\220’ in program
./Prime.c:18: error: stray ‘\342’ in program
./Prime.c:18: error: stray ‘\225’ in program
./Prime.c:18: error: stray ‘\220’ in program
./Prime.c:19: error: stray ‘\342’ in program
./Prime.c:19: error: stray ‘\225’ in program
./Prime.c:19: error: stray ‘\220’ in program
./Prime.c:19: error: stray ‘\342’ in program
./Prime.c:19: error: stray ‘\225’ in program
./Prime.c:19: error: stray ‘\220’ in program
./Prime.c:19: error: stray ‘\342’ in program
./Prime.c:19: error: stray ‘\225’ in program
./Prime.c:19: error: stray ‘\220’ in program
./Prime.c: In function ‘int main()’:
./Prime.c:18: error: ‘getch’ was not declared in this scope
0
-comrade-
357 / 358 / 167
Регистрация: 11.06.2010
Сообщений: 703
11.04.2011, 16:56 4
wcl.AleX, какой у вас компилятор???
0
wcl.AleX
0 / 0 / 0
Регистрация: 08.04.2011
Сообщений: 9
11.04.2011, 21:14  [ТС] 5
alex@Alex:~$ g++ ./Prime.c -lm -lgmp -o ./Prime
gcc -lgmp program.c
а какой нужен?
0
-comrade-
357 / 358 / 167
Регистрация: 11.06.2010
Сообщений: 703
11.04.2011, 23:44 6
Не знаю, какой больше нравится.
У вас почему-то нет библиотеки <conio.h>.

C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include <stdio.h>
 
bool simple (int n) 
{
    if(n==1) return 0;
    for( int i=2;i<=n/2;i++) if(!(n%i)) return 0;
    return 1;
}
 
int main() 
{
      int n;
      printf("  N=");
      scanf("%d",&n);
      if(simple(n)) printf("  Yes");
      else printf("  No");
      return 0;
};
1
wcl.AleX
0 / 0 / 0
Регистрация: 08.04.2011
Сообщений: 9
12.04.2011, 05:02  [ТС] 7
а как её скачать из интернета?

Добавлено через 4 часа 24 минуты
Оказывается нет библиотеки <conio.h> под Линукс. Узнал с вашего форума)
conio.h
Зато другая программа отлично работает. Спасибо большое! Ты первый кто мне дал мне работающую версию этой программы! Я даже не знаю какими словами выразить свою благодарность!
Возник ещё один вопрос
Можно ли написать такую программу в с++ чтобы она подряд проверяла на простоту от заданного числа. Например, я задаю число 90, а программа выдаёт 97?
Или я задаю 10^3000, а она выдаёт 10^3000+1027 или как то так?
0
slice
63 / 78 / 6
Регистрация: 04.11.2010
Сообщений: 249
12.04.2011, 08:14 8
Цитата Сообщение от wcl.AleX Посмотреть сообщение
Числа поряка 10^5000---10^20000 за приемлемое время?
если ты сможешь сделать это для таких больших чисел за приемлемое время, то тебе дадут Нобелевскую премию.
1
Байт
Эксперт C
18318 / 12029 / 2506
Регистрация: 24.12.2010
Сообщений: 24,293
12.04.2011, 08:53 9
Цитата Сообщение от slice Посмотреть сообщение
если ты сможешь сделать это для таких больших чисел за приемлемое время, то тебе дадут Нобелевскую премию.
Ну, это зависит от того, какое время считать приемлемым.
Ведь мы играем не для денег, нам лишь бы вечность провести...
0
wcl.AleX
0 / 0 / 0
Регистрация: 08.04.2011
Сообщений: 9
12.04.2011, 10:31  [ТС] 10
Ничего мне не дали, пока что, а о своём методе я уже давно заявлял, просто это никому не нужно.
Кому интересно может почитать.
http://dxdy.ru/topic30901.html
0
Nameless One
Эксперт С++
5786 / 3435 / 351
Регистрация: 08.02.2010
Сообщений: 7,448
12.04.2011, 10:55 11
conio.h - это библиотека консольного ввода-вывода под DOS (CONsole Input/Output). Естественно, что под linux (да и под windows, в принципе) она никому не нужна. Поэтому нужно просто удалить из исходников подключение conio.h и вызов getch.
По поводу компиляции - g++ это компилятор для С++, а у исходников на C++ обычно такие расширения: .cpp, .cxx, .cc, .C.
Так как эта программа написана скорее на C, чем на C++, то логично для компиляции использовать gcc вместо g++ (хотя и g++ должен такой исходник откомпилировать), только следует учесть, что в актуальном стандарте языка нет типа bool, он есть только в С99 (можно включить опцией -std=c99), и заменить bool на int.
Также нет смысла в данном случае у опций -lm и -lgmp.

Не по теме:

компилировать исходники вручную - не труъ. Лучше использовать make-файлы :)

0
wcl.AleX
0 / 0 / 0
Регистрация: 08.04.2011
Сообщений: 9
12.04.2011, 12:29  [ТС] 12
Спасибо, за информацию. А как изменить программу чтобы она искала простые числа, от заданного.
Например задаём её число 90, а программа выдала 97?
Или 10^3000 , а она 10^3000+1027?
Чтобы не нужно было каждый раз самому вводить число на проверку?
0
Nameless One
Эксперт С++
5786 / 3435 / 351
Регистрация: 08.02.2010
Сообщений: 7,448
12.04.2011, 14:45 13
wcl.AleX, цикл от этого числа и до того, как не найдем простое число
0
wcl.AleX
0 / 0 / 0
Регистрация: 08.04.2011
Сообщений: 9
12.04.2011, 15:52  [ТС] 14
Насколько я знаю циклы реализовываются с помощью команд For, условие If - else
Но как совместить их в этой программе?
0
diagon
Higher
1937 / 1203 / 120
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
12.04.2011, 15:58 15
Не только, из циклов есть еще while и do { } while
в данном случае
C++
1
2
for (i=a;i<=b;i++)//а-число, от которого ведется отсчет, b-конечное число
if (проверка на простоту) printf("%d\n",i);
0
Nameless One
Эксперт С++
5786 / 3435 / 351
Регистрация: 08.02.2010
Сообщений: 7,448
12.04.2011, 16:08 16
wcl.AleX, циклы можно организовывать с помощью конструкций for, while, а также с помощью рекурсивных функций.
0
wcl.AleX
0 / 0 / 0
Регистрация: 08.04.2011
Сообщений: 9
12.04.2011, 17:01  [ТС] 17
Да это я знаю, просто не знаю как будет выглядеть программа полностью , если её скомпановать

Добавлено через 47 секунд
Хотя уже и это понял
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>
 
using namespace std;
 
bool simple (int n) 
{
    if(n==1) return 0;
    for(int i=2;i<=n/2;i++) if(!(n%i)) return 0;
    return 1;
}
 
int main() 
{
    setlocale(0,"");
    int n,i;
    cout<<"  Введите число: ";
    cin>>n;
    for(i=n+1; ;i++) if(simple(i)) break;
    cout<<"  Следующее простое число после "<<n<<": "<<i<<endl;
    if(simple(n)) cout<<"  Кстати, число "<<n<<" также простое."<<endl;
    system("pause");
    return 0;
};
Добавлено через 1 минуту
Правда не сам)

Добавлено через 35 минут
Жаль что пока не работает(
0
prazuber
110 / 110 / 13
Регистрация: 29.04.2010
Сообщений: 240
12.04.2011, 17:19 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
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
// prime number computation by Erwin Unruh
 
template <int p, int i>
class is_prime {
  public:
    enum { prim = (p==2) || (p%i) && is_prime<(i>2?p:0),i-1>::prim
         }; 
}; 
 
template<>
class is_prime<0,0> {
  public:
    enum {prim=1};
}; 
 
template<>
class is_prime<0,1> {
  public:
    enum {prim=1};
}; 
 
template <int i>
class D {
  public:
    D(void*);
}; 
 
template <int i>
class Prime_print {      // primary template for loop to print prime numbers
  public:
    Prime_print<i-1> a; 
    enum { prim = is_prime<i,i-1>::prim
         }; 
    void f() {
        D<i> d = prim ? 1 : 0;
        a.f();
    } 
}; 
 
template<>
class Prime_print<1> {   // full specialization to end the loop
  public:
    enum {prim=0}; 
    void f() {
        D<1> d = prim ? 1 : 0;
    }; 
}; 
 
#define NUMBER 96
 
int main()
{
    Prime_print<NUMBER> a; 
    a.f(); 
}
Как вариант
0
Nameless One
Эксперт С++
5786 / 3435 / 351
Регистрация: 08.02.2010
Сообщений: 7,448
12.04.2011, 17:24 19
PraZuBeR, конечно, вычисления на этапе компиляции - это круто, только вот никакого практического применения у них нету.
0
Aleksandra09
0 / 0 / 0
Регистрация: 29.09.2013
Сообщений: 1
02.10.2013, 17:46 20
Помогите написать программу в с++, просто алгоритм и обоснование его!!! Задание: написать программу, которая будет запрашивать число у пользователя число от 1 до 7. программа должна проверять это условие соответствия. если пользователь вводит отличное от 1 до 7 число, то программа выдает ошибку до тех пор, пока не введешь правильное число в диапазоне от 1 до 7. по результатам введенного числа программа должна выводить на экран название дня недели. выполнить проверку двумя условными операторами одновременно!
0
02.10.2013, 17:46
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
02.10.2013, 17:46

Проверка числа на простоту
Почему, если необ. проверить, является ли число простым(напр. ч-ло n),можно...

Проверка числа на простоту
Дано натуральное число N, проверить, простое оно или нет. Увеличить его...

Проверка числа на простоту
Написать программу, которая запрашивает массив натуральных чисел (ввод с...


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

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

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