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

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

Войти
Регистрация
Восстановить пароль
 
 
Рейтинг: Рейтинг темы: голосов - 47, средняя оценка - 4.72
wcl.AleX
0 / 0 / 0
Регистрация: 08.04.2011
Сообщений: 9
#1

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

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

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

Проверка чисел на простоту - C++
сам код #include "stdafx.h" #include "iostream" #include "vector" using namespace std; int f(int n) { vector<char>...

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

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

Проверка числа на простоту - C++
Почему, если необ. проверить, является ли число простым(напр. ч-ло n),можно просматривать делители не от 2 до n, а от 2 до sqrt(n)? P.S....

Проверка на простоту числа - C++
как мне сделать так, чтобы узнать простое является число или составное, не через bool, а как-нибудь через оператор switch case: т е, case...

Проверка числа на простоту - C++
Помогите решить 2 задачки, пожалуйста, 1. Написать программу для проверки натурального числа N на простоту. N вводится с клавиатуры. ...

19
-comrade-
355 / 356 / 42
Регистрация: 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-
355 / 356 / 42
Регистрация: 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-
355 / 356 / 42
Регистрация: 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;
};
0
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
35 / 78 / 4
Регистрация: 04.11.2010
Сообщений: 249
12.04.2011, 08:14 #8
Цитата Сообщение от wcl.AleX Посмотреть сообщение
Числа поряка 10^5000---10^20000 за приемлемое время?
если ты сможешь сделать это для таких больших чисел за приемлемое время, то тебе дадут Нобелевскую премию.
1
Байт
Эксперт C
16548 / 10818 / 1640
Регистрация: 24.12.2010
Сообщений: 20,888
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
Эксперт С++
5775 / 3425 / 255
Регистрация: 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
Эксперт С++
5775 / 3425 / 255
Регистрация: 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
1930 / 1196 / 49
Регистрация: 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
12.04.2011, 15:58
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
12.04.2011, 15:58
Привет! Вот еще темы с ответами:

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

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

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

Проверка числа на простоту - C++
Дано натуральное число n&gt;1. Проверьте, является ли оно простым. Программа должна вывести слово YES, если число простое и NO, если число...


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

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

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