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

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

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 47, средняя оценка - 4.72
wcl.AleX
0 / 0 / 0
Регистрация: 08.04.2011
Сообщений: 9
08.04.2011, 10:34     [Cи] Проверка чисел на простоту #1
Как в Си написать программу, которая проверяла бы вводимые числа на простоту вероятностными методами. Числа поряка 10^5000---10^20000 за приемлемое время?
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
08.04.2011, 10:34     [Cи] Проверка чисел на простоту
Посмотрите здесь:

Проверка чисел на простоту C++
Проверка на простоту числа C++
Проверка числа на простоту C++
C++ ПРоверка числа на простоту
C++ Проверка числа на простоту
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
-comrade-
355 / 356 / 42
Регистрация: 11.06.2010
Сообщений: 703
11.04.2011, 16:34     [Cи] Проверка чисел на простоту #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;
};
wcl.AleX
0 / 0 / 0
Регистрация: 08.04.2011
Сообщений: 9
11.04.2011, 16:50  [ТС]     [Cи] Проверка чисел на простоту #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
-comrade-
355 / 356 / 42
Регистрация: 11.06.2010
Сообщений: 703
11.04.2011, 16:56     [Cи] Проверка чисел на простоту #4
wcl.AleX, какой у вас компилятор???
wcl.AleX
0 / 0 / 0
Регистрация: 08.04.2011
Сообщений: 9
11.04.2011, 21:14  [ТС]     [Cи] Проверка чисел на простоту #5
alex@Alex:~$ g++ ./Prime.c -lm -lgmp -o ./Prime
gcc -lgmp program.c
а какой нужен?
-comrade-
355 / 356 / 42
Регистрация: 11.06.2010
Сообщений: 703
11.04.2011, 23:44     [Cи] Проверка чисел на простоту #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;
};
wcl.AleX
0 / 0 / 0
Регистрация: 08.04.2011
Сообщений: 9
12.04.2011, 05:02  [ТС]     [Cи] Проверка чисел на простоту #7
а как её скачать из интернета?

Добавлено через 4 часа 24 минуты
Оказывается нет библиотеки <conio.h> под Линукс. Узнал с вашего форума)
conio.h
Зато другая программа отлично работает. Спасибо большое! Ты первый кто мне дал мне работающую версию этой программы! Я даже не знаю какими словами выразить свою благодарность!
Возник ещё один вопрос
Можно ли написать такую программу в с++ чтобы она подряд проверяла на простоту от заданного числа. Например, я задаю число 90, а программа выдаёт 97?
Или я задаю 10^3000, а она выдаёт 10^3000+1027 или как то так?
slice
32 / 75 / 4
Регистрация: 04.11.2010
Сообщений: 249
12.04.2011, 08:14     [Cи] Проверка чисел на простоту #8
Цитата Сообщение от wcl.AleX Посмотреть сообщение
Числа поряка 10^5000---10^20000 за приемлемое время?
если ты сможешь сделать это для таких больших чисел за приемлемое время, то тебе дадут Нобелевскую премию.
Байт
 Аватар для Байт
13940 / 8771 / 1219
Регистрация: 24.12.2010
Сообщений: 15,869
12.04.2011, 08:53     [Cи] Проверка чисел на простоту #9
Цитата Сообщение от slice Посмотреть сообщение
если ты сможешь сделать это для таких больших чисел за приемлемое время, то тебе дадут Нобелевскую премию.
Ну, это зависит от того, какое время считать приемлемым.
Ведь мы играем не для денег, нам лишь бы вечность провести...
wcl.AleX
0 / 0 / 0
Регистрация: 08.04.2011
Сообщений: 9
12.04.2011, 10:31  [ТС]     [Cи] Проверка чисел на простоту #10
Ничего мне не дали, пока что, а о своём методе я уже давно заявлял, просто это никому не нужно.
Кому интересно может почитать.
http://dxdy.ru/topic30901.html
Nameless One
Эксперт С++
 Аватар для Nameless One
5753 / 3402 / 255
Регистрация: 08.02.2010
Сообщений: 7,390
12.04.2011, 10:55     [Cи] Проверка чисел на простоту #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-файлы

wcl.AleX
0 / 0 / 0
Регистрация: 08.04.2011
Сообщений: 9
12.04.2011, 12:29  [ТС]     [Cи] Проверка чисел на простоту #12
Спасибо, за информацию. А как изменить программу чтобы она искала простые числа, от заданного.
Например задаём её число 90, а программа выдала 97?
Или 10^3000 , а она 10^3000+1027?
Чтобы не нужно было каждый раз самому вводить число на проверку?
Nameless One
Эксперт С++
 Аватар для Nameless One
5753 / 3402 / 255
Регистрация: 08.02.2010
Сообщений: 7,390
12.04.2011, 14:45     [Cи] Проверка чисел на простоту #13
wcl.AleX, цикл от этого числа и до того, как не найдем простое число
wcl.AleX
0 / 0 / 0
Регистрация: 08.04.2011
Сообщений: 9
12.04.2011, 15:52  [ТС]     [Cи] Проверка чисел на простоту #14
Насколько я знаю циклы реализовываются с помощью команд For, условие If - else
Но как совместить их в этой программе?
diagon
Higher
 Аватар для diagon
1920 / 1186 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
12.04.2011, 15:58     [Cи] Проверка чисел на простоту #15
Не только, из циклов есть еще while и do { } while
в данном случае
C++
1
2
for (i=a;i<=b;i++)//а-число, от которого ведется отсчет, b-конечное число
if (проверка на простоту) printf("%d\n",i);
Nameless One
Эксперт С++
 Аватар для Nameless One
5753 / 3402 / 255
Регистрация: 08.02.2010
Сообщений: 7,390
12.04.2011, 16:08     [Cи] Проверка чисел на простоту #16
wcl.AleX, циклы можно организовывать с помощью конструкций for, while, а также с помощью рекурсивных функций.
wcl.AleX
0 / 0 / 0
Регистрация: 08.04.2011
Сообщений: 9
12.04.2011, 17:01  [ТС]     [Cи] Проверка чисел на простоту #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 минут
Жаль что пока не работает(
prazuber
108 / 108 / 3
Регистрация: 29.04.2010
Сообщений: 240
12.04.2011, 17:19     [Cи] Проверка чисел на простоту #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(); 
}
Как вариант
Nameless One
Эксперт С++
 Аватар для Nameless One
5753 / 3402 / 255
Регистрация: 08.02.2010
Сообщений: 7,390
12.04.2011, 17:24     [Cи] Проверка чисел на простоту #19
PraZuBeR, конечно, вычисления на этапе компиляции - это круто, только вот никакого практического применения у них нету.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
02.10.2013, 17:46     [Cи] Проверка чисел на простоту
Еще ссылки по теме:

C++ Проверка числа на простоту
C++ Проверка чисел на простоту и проверку на наличие общих цифр в записи
проверка числа на простоту C++

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

Или воспользуйтесь поиском по форуму:
Aleksandra09
Сообщений: n/a
02.10.2013, 17:46     [Cи] Проверка чисел на простоту #20
Помогите написать программу в с++, просто алгоритм и обоснование его!!! Задание: написать программу, которая будет запрашивать число у пользователя число от 1 до 7. программа должна проверять это условие соответствия. если пользователь вводит отличное от 1 до 7 число, то программа выдает ошибку до тех пор, пока не введешь правильное число в диапазоне от 1 до 7. по результатам введенного числа программа должна выводить на экран название дня недели. выполнить проверку двумя условными операторами одновременно!
Yandex
Объявления
02.10.2013, 17:46     [Cи] Проверка чисел на простоту
Ответ Создать тему
Опции темы

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