найти простые числа
Нужно написать програмку, которая выводит на экран простые числа от 1 до 10000, не используя массивы. Я запуталась. Простые, это те которые делятся на 1 и на само себя.
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
Ответы с готовыми решениями:
Найти все трехзначные простые числа. Определить функцию позволяющую распознавать простые числа
Найти все трехзначные простые числа. Определить функцию позволяющую распознавать простые числа.
Найти числа-близнецы: простые числа разность между которыми равна 2
Дано натуральное число n. Среди чисел n, n + 1, …, 2n найти все числа-близнецы: простые числа.
Найти простые числа с суммой цифр меньше заданного числа
нужно написать прогу, можно использовать только циклы. Если можно, с объяснениями. Условие: Найти.
2255 / 770 / 25
Регистрация: 27.05.2008
Сообщений: 1,496
Напиши функцию,которая проверяет,простое ли это число.
1 2 3 4
int simple(int n){ for(int i=2;i n/2;i++) if( (n%i)==0 ) return 0; return 1; }
Потом в программе вызывай ее в цикле от 2 до 10000
1 2 3 4
int main() { for(int i=2;i 10000;i++) if(simple(i)) printf("%d ", i); return 0; };
Регистрация: 07.01.2009
Сообщений: 4
я еще до заглядывания на форум поняла свою ошибку, но все равно, спасибки )
А сделать то же самое но без испльзования функций (только «void main»)?
712 / 495 / 49
Регистрация: 15.01.2009
Сообщений: 1,720
например так:
1 2 3 4 5 6 7 8 9 10
void main() { int f=0; for (int j=2; j 10000; j++) { for(int i=2;i j/2;i++) if( (n%j)==0 ) {f=1; break;} if(f == 0) printf("%d ", j); f=0; } return; };
Временно недоступен
957 / 228 / 14
Регистрация: 12.04.2009
Сообщений: 926
Тут можно улучшить немного.
1 2 3 4 5 6 7 8
int simple(int n){ int sq=(int) sqrt(n); if (n%2 != 0) for(int i=3;i sq;i+=2) if( (n%i)==0 ) return 0; if(n%2 == 0) return 0; return 1; }
247 / 205 / 26
Регистрация: 03.02.2009
Сообщений: 785
извините, описался.
2923 / 844 / 324
Регистрация: 30.04.2009
Сообщений: 2,633
Сообщение от #pragma 
Тут можно улучшить немного.
я согласен, надо проверять до корня числа
7175 / 3234 / 81
Регистрация: 17.06.2009
Сообщений: 14,164
Тут можно улучшить немного.
В результате улучшения стало неправильно.
Проверять нужно до корня включительно !
1 2 3 4 5 6 7 8 9 10 11 12 13
int simple_true( int n ) { int i, sq; if ( n%2==0 ) { return 0; } sq= (int)sqrt( n ); for ( i= 3; isq; i++ ) { if ( (n%i) == 0 ) { return 0; } } return 1; } /* simple_true() */
Регистрация: 15.04.2012
Сообщений: 185
Сообщение от odip
В результате улучшения стало неправильно.
Проверять нужно до корня включительно !
1 2 3 4 5 6 7 8 9 10 11 12 13
int simple_true( int n ) { int i, sq; if ( n%2==0 ) { return 0; } sq= (int)sqrt( n ); for ( i= 3; isq; i++ ) { if ( (n%i) == 0 ) { return 0; } } return 1; } /* simple_true() */
Может кто-нибудь алгоритм проверки простого числа написать? Т.е. словами.
интересны способы.
4267 / 2241 / 203
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
Сообщение от #pragma
Тут можно улучшить немного.
похвально можно еще больше улучшить
Быстрая проверка натурального числа на простоту
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
Помогаю со студенческими работами здесь
Найти все натуральные числа, меньшие заданного числа и взаимно простые с ним
Дано натуральное число n. Необходимо получить все натуральные числа, меньшие nn и взаимно простые с.
Найти простые числа, которые можно разбить еще на два простых числа
Найти на промежутке количество простых чисел, которые можно разбить еще на два простых числа. К.
Найти сверхпростые числа: простые числа, номера которых являются простыми числами.
Привет родные форумчане! Пожалуйста помогите решить буду особенно благодарен если напишите код с.
Найти все простые числа меньшие заданного числа
Помогите Пожалуйста! Простое число это число которое делится только на 1 и на самого себя.
Простое число
Простое число – это натуральное число, которое делиться без остатка на себя и на единицу.
Метод для проверки, является ли число простым
Исходя из определения простоты числа, напишем метод для проверки.
Простое число должно удовлетворять условиям:
- Быть больше единицы – условие проверим с помощью условного оператора if;
- Делиться нацело только на один и на себя – в цикле проверим делиться ли N нацело на числа из диапазона от 2 до N-1.
public static bool IsPrimeNumber(uint n) < var result = true; if (n > 1) < for (var i = 2u; i < n; i++) < if (n % i == 0) < result = false; break; > > > else < result = false; > return result; > Если число, которое передается в качестве аргумента метода, является простым, метод возвращает значение true и false в противном случае.
Использование метода для проверки числа N на простоту
Простые числа из диапазона от 0 до N
Используя метод для проверки, можем вывести на экран все простые числа из промежутка от 0 до N.
Программа позволяющая вывести простые числа из отрезка:
static void Main(string[] args) < Console.Write("N hljs-keyword">var n = Convert.ToUInt32(Console.ReadLine()); Console.WriteLine("Простые числа из диапазона (, )", 0, n); for (var i = 0u; i < n; i++) < if (IsPrimeNumber(i)) < Console.Write($" "); > > Console.ReadLine(); > Результат работы программы:
N первых простых чисел
После небольшой модификации программы, можем вывести необходимое количество простых чисел.
Программа позволяющая вывести на экран N первых простых чисел:
static void Main(string[] args) < Console.Write("N hljs-keyword">var n = Convert.ToUInt32(Console.ReadLine()); Console.WriteLine(" первых простых чисел", n); var count = 0u; var i = 0u; while (count < n) < if (IsPrimeNumber(i)) < Console.Write(i); if (count < n - 1) < Console.Write(", "); > count++; > i++; > Console.ReadLine(); > Результат работы программы:
Является ли число простым
Хочу написать прогу на C++. Она сначала просит ввести число (простое оно или нет, прога проверяет), потом выводит результат на консоль. Объясните, пожалуйста, как сделать или хоть намекните (среда dev-c++ 4.9.9.2), очень прошу.
Отслеживать
80.6k 9 9 золотых знаков 78 78 серебряных знаков 134 134 бронзовых знака
задан 16 ноя 2011 в 12:40
инклюде димо инклюде димо
45 1 1 золотой знак 1 1 серебряный знак 4 4 бронзовых знака
8 ответов 8
Сортировка: Сброс на вариант по умолчанию
Написать что-то в виде
int n; // ввести n c клавиатуры for (i = 2; i > //вывести что n простое. return 0; Алгоритм, конечно, можно заметно ускорить, как минимум в два раза, но для начала хватит.
Отслеживать
29.7k 3 3 золотых знака 16 16 серебряных знаков 54 54 бронзовых знака
ответ дан 16 ноя 2011 в 13:01
112k 6 6 золотых знаков 93 93 серебряных знака 159 159 бронзовых знаков
должно быть i<=sqrt(n), иначе квадрат простого числа тоже будет простым.
16 ноя 2011 в 14:14
Тогда, наверное, даже лучше набросить сверху единицу, то есть i
16 ноя 2011 в 14:36
Поправь ответ? И ещё нехорошо на каждой итерации квадратный корень считать.
17 окт 2017 в 15:45
А можно проверять делимость по простым числам. А найти их в не очень большом количестве особого труда не составит. =)
Решето Эратосфена (до корня из n). За 1 секунду находит числа до 10^7 примерно.
А дальше перебор делимости (Либо если число уже найдено Эратосфеном, то и перебирать не придётся) на простые числа, если число больше чем 10^7 также до корня из n.
И всё довольно просто и быстро =)
Отслеживать
ответ дан 21 ноя 2011 в 13:03
147 13 13 бронзовых знаков
Довольна старая тема, но всё же добавлю. Есть одна особенность простых чисел — при возведении числа в квадрат, деление этого числа в квадрате на 24 будет давать остаток 1 ( c 2 и 3 не работает, т.к они слишком маленькие , но с остальными числами работает отлично и не тратит много ресурсов для проверки)
int isprime(int num) < if ((num * num) % 24 == 1) < return true; >return false; > Отслеживать
3,125 6 6 золотых знаков 18 18 серебряных знаков 33 33 бронзовых знака
ответ дан 16 июл 2019 в 10:23
user344423 user344423
И не только простых, но и составных, что делает данный алгоритм непригодным для определения простых чисел
16 июл 2019 в 11:00
Это не работает с составными числами, только с простыми.youtube.com/watch?v=ZMkIiFs35HQ
– user344423
16 июл 2019 в 21:01
25, 35, 49, 55, 65, 77, 85, 91, 95 и ещё бесконечное количество чисел, которая ваша функция определяет как простые
16 июл 2019 в 21:22
Плюс к тому, кроме 2 и 3, с простого числа 46349 и последующие простые числа определяет как составные
16 июл 2019 в 21:43
В плане эффективности могут намекнуть, например, на тест Рабина-Миллера, но судя по всему, Вам будет проще реализовать проверку тривиальным делением
Отслеживать
ответ дан 16 ноя 2011 в 12:52
3,978 12 12 серебряных знаков 7 7 бронзовых знаков
bool prime(ll n) < for (ll i = 2; i return true; > Отслеживать
19.1k 6 6 золотых знаков 30 30 серебряных знаков 44 44 бронзовых знака
ответ дан 16 июн 2015 в 17:19
Елдан Абдрашим Елдан Абдрашим
И правильно минуснули. Зачем в цикле проверять делимость на четные?
16 июн 2015 в 19:03
#include #include using namespace std; int main()< int n, i; bool isPrime = true; cout>n; cout > if(isPrime) cout
Это готовый код
Отслеживать
5,199 4 4 золотых знака 27 27 серебряных знаков 51 51 бронзовый знак
ответ дан 17 окт 2017 в 15:40
Bogdan Pahomov Bogdan Pahomov
46 7 7 бронзовых знаков
В первом ответе допущена неточность. Я бы написал так
bool prostoNumer(int n)
PS: дело в том что пропускает 4. Потому что цикл не работает sqrt(4) == 2, 2 < 2 и поэтому цикл завершает работу с ложным результатом. нужно поправить 2 Отслеживать 845 6 6 серебряных знаков 12 12 бронзовых знаков ответ дан 3 апр 2017 в 10:34 1 1 1 бронзовый знак Это есть в комментариях под принятым ответом 3 апр 2017 в 10:39
Обратите внимание на класс Prime . Простое число — число, имеющее два делителя. Это единица и само это число. Следовательно единица простым числом являться не может, так как она имеет один делитель, значит ее нужно исключить. Для этого воспользуемся условным оператором if . После этого начнем искать делители этого числа (будем перебирать все числа, которые меньше указанного числа), напомню делителем называется число, которое делится на данный делитель без остатка, то есть остаток равен 0. Когда нашли такое число, ставим на него булевое значение false, как пометка о том, что данное число является составным. После выполнения управляющей конструкции for остаются некоторые числа, которые не помечены false, то есть не имеют делителя(отличного от себя и 1), помечаем их как true.
namespace one < class Program < static void Main(string[] args) < Prime prime = new Prime(); int AmountOfNumbers = 10; for (int i = 2; i < AmountOfNumbers; i++) < if (prime.IsPrime(i)) < Console.WriteLine(i + " простое число."); >else < Console.WriteLine(i + " составное число."); >> > > class Prime < public bool IsPrime(int x) < if (x >1) < for (int i = 2; i < x; i++) < if ((x % i) == 0) < return false; >> return true; > else < return false; >> > >
Отслеживать
ответ дан 24 фев 2022 в 8:15
EkaterinaR. EkaterinaR.
59 6 6 бронзовых знаков
Код рабочий, но слишком неоптимальный, даже по сравнению с предыдущими ответами
24 фев 2022 в 9:01
Highly active question. Earn 10 reputation (not counting the association bonus) in order to answer this question. The reputation requirement helps protect this question from spam and non-answer activity.
Программирование на C, C# и Java
Уроки программирования, алгоритмы, статьи, исходники, примеры программ и полезные советы
ОСТОРОЖНО МОШЕННИКИ! В последнее время в социальных сетях участились случаи предложения помощи в написании программ от лиц, прикрывающихся сайтом vscode.ru. Мы никогда не пишем первыми и не размещаем никакие материалы в посторонних группах ВК. Для связи с нами используйте исключительно эти контакты: vscoderu@yandex.ru, https://vk.com/vscode
Является ли число простым — Проверяем на языке Си
Напишем на языке Си программу, проверяющую является ли число простым. Для проверки будем использовать простейший алгоритм, основанный непосредственно на определении простого числа.
Простое число — определение
Простое число — это натуральное число (то есть целое и положительное), большее, чем единица, которое делится без остатка только на единицу и само на себя.
Список простых чисел (приведем до ста) начинается так: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97…
Функция на Си, проверяющая — является ли число простым
Напишем на языке Си функцию, которая будет проверять — простое ли число. И возвращать результат проверки в виде логической величины bool: true (да) или false (нет).
// функция проверяет — простое ли число n
bool isPrime ( int n )
// в цикле перебираем числа от 2 до n — 1
for ( int i = 2 ; i < n ; i ++ )
if ( n % i == 0 ) // если n делится без остатка на i - возвращаем false (число не простое)
return false ;
// если программа дошла до данного оператора, то возвращаем true (число простое) - проверка пройдена
return true ;
else // иначе возвращаем false (число не простое)
return false ;
Алгоритм проверки числа n на простоту строится на определении термина простого числа.
Во-первых число n должно быть больше 1 (проверяем это в строке 5 с помощью условного оператора if), а во-вторых проверяемое число должно иметь только два делителя: 1 и n (проверяем это в строках 8-10 с помощью цикла for и оператора if).
Для работы данного метода требуется подключить заголовочный файл stdbool.h в начале файла с исходным кодом. В stdbool.h содержится определение логических констант true и false, поскольку в чистой версии языка Си они отсутствуют.
Для подключения используем директиву include: