Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
Блоги Сообщество Поиск Заказать работу  
 
Рейтинг 4.67/21: Рейтинг темы: голосов - 21, средняя оценка - 4.67
0 / 0 / 0
Регистрация: 13.06.2020
Сообщений: 8

Составить функцию, находящую следующее за N простое число

21.06.2020, 17:21. Показов 4239. Ответов 15

Студворк — интернет-сервис помощи студентам
Дано простое число N. Составить функцию, находящую следующее за N простое число. Если входное данное не является простым числом, то функция должна возвращать ноль.
Объясните мне пожалуйста, к примеру я ввел 7, т.е. следующее простое число будет 8 или что?
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <iostream>
#include <cstdlib>
#include <locale.h>
using namespace std;
int main ()
{
setlocale(0,"Rus");
int N, s;
cout << "Введите простое число" <<endl;
cout << "N=";
cin >> N;
int c=1;
N++;
for(int i=2;i<=N;i++)
{
if(N%i==0)
c++;
if (c==2)
cout <<N<< endl;
}
return 0;
}
0
Лучшие ответы (1)
cpp_developer
Эксперт
20123 / 5690 / 1417
Регистрация: 09.04.2010
Сообщений: 22,546
Блог
21.06.2020, 17:21
Ответы с готовыми решениями:

Дано простое число. Составить функцию, которая будет находить следующее за ним простое число
Дано простое число. Составить функцию, которая будет находить следующее за ним простое число.

Дано простое число. Составить функцию, которая будет находить следующее за ним простое число
Дано простое число. Составить функцию, которая будет находить следующее за ним простое число

Дано простое число. Составить функцию,которая будет находить следующее за ним простое число
Дано простое число. Составить функцию, которая будет находить следующее за ним простое число.

15
458 / 294 / 191
Регистрация: 23.06.2018
Сообщений: 678
21.06.2020, 17:44
Цитата Сообщение от GPedro Посмотреть сообщение
к примеру я ввел 7, т.е. следующее простое число будет 8 или что?
Следующее простое число будет 11... Извините, но вы знаете что такое простое число?

Добавлено через 12 минут
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
// Функция
int func(int n)
{
    // Проверка данного числа
    bool prime = n % 2;
    int s = sqrt(n);
    for (int i = 3; i <= s && prime; i += 2)
        prime = prime && (n % i);
 
    // Возврат нуля если число не простое
    if (!prime)
        return 0;
 
    // Поиск следующего простого числа
    do
    {
        n += 2;
        prime = true;
        s = sqrt(n);
        for (int i = 3; i <= s && prime; i += 2)
            prime = prime && (n % i);
    } while (!prime);
    return n;
}
0
0 / 0 / 0
Регистрация: 13.06.2020
Сообщений: 8
22.06.2020, 10:48  [ТС]
Bleach163, Давно не встречался может, я уже с этого много чего позабывал, теперь вспомнил, спасибо за помощь
0
Диссидент
Эксперт C
 Аватар для Байт
27714 / 17332 / 3810
Регистрация: 24.12.2010
Сообщений: 38,978
22.06.2020, 11:09
Лучший ответ Сообщение было отмечено GPedro как решение

Решение

Bleach163, я бы не стал рекомендовать ваш код к использованию. Помимо того, что он ошибочен (при n=1,2 дает неверный результат), он бы мог занять призовое место по нелепости алгоритма определения простоты.
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
bool isPrime(unsigned n)
{
   if (n < 2) return false;
   if (n==2) return true;
   for(int i = 3; i*i <= n; i+=2)
      if (n%i==0) return false;
   return true;
}
int func(unsigned N)
{
   if (!isPrime(N)) return 0;
   for(int i=N+1; ; i++)
      if (isPrime(i)) return i;
}
1
458 / 294 / 191
Регистрация: 23.06.2018
Сообщений: 678
26.06.2020, 00:52
Байт, я знаю, я очень своевременно, но вот я вернулся в эту тему чтобы быстренько скопировать вашу функцию проверки... И обнаружил, что не хватает деления на 2.
Так что для тех, кто каким-то образом попал на конкретно эту тему:
C++
1
2
3
4
5
6
7
8
bool isPrime(unsigned n)
{
   if (n==2) return true;
   if (n<2 || n%2==0) return false;
   for(unsigned i = 3; i*i <= n; i+=2)
      if (n%i==0) return false;
   return true;
}
Хотя до сих пор не понимаю, почему постоянно делать i*i лучше, чем один раз sqrt(n).
1
863 / 513 / 215
Регистрация: 19.01.2019
Сообщений: 1,216
26.06.2020, 02:11
C++
1
2
3
4
5
6
7
8
9
bool isPrime(unsigned n)
{
    if (n < 2) return false;
    if (n == 2) return true;
    if (n % 2 == 0) return false;
    for (int i = 3; i * i <= n; i += 2)
        if (n % i == 0) return false;
    return true;
}
0
Диссидент
Эксперт C
 Аватар для Байт
27714 / 17332 / 3810
Регистрация: 24.12.2010
Сообщений: 38,978
26.06.2020, 11:05
Цитата Сообщение от Bleach163 Посмотреть сообщение
не хватает деления на 2.
Да, моя промашка. Спасибо, что поправили
Цитата Сообщение от Bleach163 Посмотреть сообщение
почему постоянно делать i*i лучше, чем один раз sqrt(n).
Тут вопрос спорный. Я считаю, что если задача целочисленная, то привлекать плавающую арифметику - грех. И возможная потеря точности. Во всяком случае для привлечения ее должны быть веские основания. А небольшое, процентное сокращение времени, лично я основанием не считаю. Хотя могут быть и другие точки зрения, и другие задачи, где этот процентик дорог.

Добавлено через 15 минут
Bleach163, хочу пояснить свои слова насчет потери точности. Вот sqrt(1000000). Это число типа double. Вы уверены, что оно будет ровно 1000.000000 ? А не 1000.0000001 или 999.99999999 ? Я не уверен. Все зависит от реализации. И если в первом случае все хорошо, то во втором будет ошибка.
Конечно, в данном случае это можно обойти, используя s = sqrt(n) + 1. Но на фига мне такие размышления?
2
 Аватар для Annemesski
2670 / 1333 / 479
Регистрация: 08.11.2016
Сообщений: 3,679
26.06.2020, 14:06
Цитата Сообщение от Байт Посмотреть сообщение
Конечно, в данном случае это можно обойти, используя s = sqrt(n) + 1
s = sqrt(n) + 0.5 - для округления к ближайшему, с единицей
Цитата Сообщение от Байт Посмотреть сообщение
А не 1000.0000001 или 999.99999999 ?
в первом случае получим 1001
0
Диссидент
Эксперт C
 Аватар для Байт
27714 / 17332 / 3810
Регистрация: 24.12.2010
Сообщений: 38,978
26.06.2020, 16:16
Цитата Сообщение от Annemesski Посмотреть сообщение
в первом случае получим 1001
Это не страшно. В хучшем случае получаем лишнюю итерацию в цикле. Но решения это не портит.
0
736 / 700 / 110
Регистрация: 29.05.2015
Сообщений: 4,266
26.06.2020, 16:34
Не так давно была тема, где выложили прекрасный шустрый код проверки на простоту делением. Минимум в 2 раза быстрее простого деления. Зачем изобретать велосипед?
0
Диссидент
Эксперт C
 Аватар для Байт
27714 / 17332 / 3810
Регистрация: 24.12.2010
Сообщений: 38,978
26.06.2020, 16:36
Цитата Сообщение от alexu_007 Посмотреть сообщение
Не так давно была тема, где выложили прекрасный шустрый код
Где тема? Где код?
0
36 / 11 / 1
Регистрация: 21.06.2020
Сообщений: 93
26.06.2020, 16:40

Не по теме:

Байт, хорошо что здесь не идет разработка программы промышленной автоматизации, а так бы уже был нанесен ущерб несколько миллионов рублей, зависимо от размеров завода :D


Я всегда предпочитаю использовать длинную арифметику (хотя она занимает больше ресурсов)
0
736 / 700 / 110
Регистрация: 29.05.2015
Сообщений: 4,266
26.06.2020, 21:54
Цитата Сообщение от Байт Посмотреть сообщение
Где тема? Где код?
C++ (Qt)
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
bool isPrime(quint64 a)
{
     quint64 i1, i2, i3, i4, i5, i6, i7, i8, bound;
 
     if (a == 0 || a == 1) return false;
 
     if (a == 2 || a == 3 || a == 5 || a == 7 || a == 11 || a == 13 || a == 17 || a == 19 || a == 23 || a == 29)
     return true;
 
     if (a%2 == 0 || a%3 == 0 || a%5 == 0 || a%7 == 0 || a%11 == 0 ||
         a%13 == 0 || a%17 == 0 || a%19 == 0 || a%23 == 0 || a%29 == 0)
         return false;
 
     bound = sqrt((double)a);
 
     i1 = 31; i2 = 37; i3 = 41; i4 = 43; i5 = 47; i6 = 49; i7 = 53; i8 = 59;
 
     while(i8 <= bound && a%i1 && a%i2 && a%i3 && a%i4 && a%i5 && a%i6 && a%i7 && a%i8)
     {
         i1 += 30; i2 += 30; i3 += 30; i4 += 30; i5 += 30; i6 += 30; i7 += 30; i8 += 30;
     }
 
     if(i8 <= bound ||
        i1 <= bound && a % i1 == 0 ||
        i2 <= bound && a % i2 == 0 ||
        i3 <= bound && a % i3 == 0 ||
        i4 <= bound && a % i4 == 0 ||
        i5 <= bound && a % i5 == 0 ||
        i6 <= bound && a % i6 == 0 ||
        i7 <= bound && a % i7 == 0)  return false;
 
     return true;
}
1
 Аватар для andrey_f
882 / 535 / 228
Регистрация: 21.02.2011
Сообщений: 5,706
26.06.2020, 22:09
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
bool isPrime(quint64 num) 
{
  if(num==2 || num ==3 || num ==5) 
   return true;  
  else if(num <=1 || num % 2 ==0 || num % 3 ==0) 
   return false;
  else
  {
    for(int i=5; i<=sqrt(num); i+=6 )
     if( (num % i==0) || (num % (i+2) == 0)) return false;  
    return true;
  }
}
0
Диссидент
Эксперт C
 Аватар для Байт
27714 / 17332 / 3810
Регистрация: 24.12.2010
Сообщений: 38,978
26.06.2020, 23:18
Цитата Сообщение от alexu_007 Посмотреть сообщение
прекрасный шустрый код
Но о-о-очень скушный. Да и шустрость его не велика. В разы, может быть... И для небольших чисел... Но это, поверьте мне, давно никому не интересно.
Да, идейку можно развить, добавив в список чисел 31, 37, 41, 43, 47 и так далее. Но представленный вами код не позволяет легко произвести эту модификацию.
Так что мы уж лучше по-старинке... На своем велосипеде...

Добавлено через 5 минут
Цитата Сообщение от andreyfreelans Посмотреть сообщение
for(int i=5; i<=sqrt(num); i+=6 )
Понимая и идею, и ваши самые лучшие намерения, не могу не отметить порочность вычисления sqrt(num) при каждой итерации цикла.
Ну это так, к основной нитке топика не относится. Так сказать, "хозяйке на заметку"

Добавлено через 5 минут
Цитата Сообщение от alexu_007 Посмотреть сообщение
i1 += 30; i2 += 30; i3 += 30; i4 += 30; i5 += 30; i6 += 30; i7 += 30; i8 += 30;
от одного этого хочется заплакать и заснуть

Добавлено через 7 минут
alexu_007, корректность и работоспособность вашего кода проверять не стал. Есть подозрения... Но не более. Например, как выпрыгнуло i6 = 49 в строке 16 ?
Но вы уж меня простите, коды, подобные этому, не предназначены для анализа. И писать такое - себя не уважать.
1
736 / 700 / 110
Регистрация: 29.05.2015
Сообщений: 4,266
27.06.2020, 07:27
Цитата Сообщение от Байт Посмотреть сообщение
Да и шустрость его не велика. В разы, может быть... И для небольших чисел... Но это, поверьте мне, давно никому не интересно.
В данном конкретном примере - да. Но из мелочей состоит крупное. Тут в 2 раза медленнее, там на 30% медленнее - и вот ваше приложение уже тормозит, требует более мощного процессора.

Если есть более быстрый алгоритм - почему бы в программе не использовать его? Хуже точно не будет.

P.S. В 2 раза быстрее - ничего себе невелика шустрость! Люди за проценты бьются...
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
raxper
Эксперт
30234 / 6612 / 1498
Регистрация: 28.12.2010
Сообщений: 21,154
Блог
27.06.2020, 07:27
Помогаю со студенческими работами здесь

Дано простое число. Составить функцию, которая будет находить следующее за ним простое число.
6.2.2. Помогите, пожалуйста, решить задачи в С++ с помощью функций. Дано простое число. Составить функцию, которая будет находить...

Дано простое число. Составить функцию,которая будет находить следующее за ним простое число.
дано простое число.составить функцию,которая будет находить следующее за ним простое число.

Дано простое число. Составить функцию, которая будет находить следующее за ним простое число
Дано простое число. Составить функцию, которая будет находить следующее за ним простое число!

Дано простое число. Составить функцию, которая будет находить следующее за ним простое число.
Дано простое число. Составить функцию, которая будет находить следующее за ним простое число.

Дано простое число. Составить функцию, которая будет находить следующее за ним простое число
Дано простое число. Составить функцию, которая будет находить следующее за ним простое число Python 2.6. пожалуйста, ничего умного)...


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

Или воспользуйтесь поиском по форуму:
16
Ответ Создать тему
Новые блоги и статьи
PhpStorm 2025.3: WSL Terminal всегда стартует в ~
and_y87 14.12.2025
PhpStorm 2025. 3: WSL Terminal всегда стартует в ~ (home), игнорируя директорию проекта Симптом: После обновления до PhpStorm 2025. 3 встроенный терминал WSL открывается в домашней директории. . .
Access
VikBal 11.12.2025
Помогите пожалуйста !! Как объединить 2 одинаковые БД Access с разными данными.
Новый ноутбук
volvo 07.12.2025
Всем привет. По скидке в "черную пятницу" взял себе новый ноутбук Lenovo ThinkBook 16 G7 на Амазоне: Ryzen 5 7533HS 64 Gb DDR5 1Tb NVMe 16" Full HD Display Win11 Pro
Музыка, написанная Искусственным Интеллектом
volvo 04.12.2025
Всем привет. Некоторое время назад меня заинтересовало, что уже умеет ИИ в плане написания музыки для песен, и, собственно, исполнения этих самых песен. Стихов у нас много, уже вышли 4 книги, еще 3. . .
От async/await к виртуальным потокам в Python
IndentationError 23.11.2025
Армин Ронахер поставил под сомнение async/ await. Создатель Flask заявляет: цветные функции - провал, виртуальные потоки - решение. Не threading-динозавры, а новое поколение лёгких потоков. Откат?. . .
Поиск "дружественных имён" СОМ портов
Argus19 22.11.2025
Поиск "дружественных имён" СОМ портов На странице: https:/ / norseev. ru/ 2018/ 01/ 04/ comportlist_windows/ нашёл схожую тему. Там приведён код на С++, который показывает только имена СОМ портов, типа,. . .
Сколько Государство потратило денег на меня, обеспечивая инсулином.
Programma_Boinc 20.11.2025
Сколько Государство потратило денег на меня, обеспечивая инсулином. Вот решила сделать интересный приблизительный подсчет, сколько государство потратило на меня денег на покупку инсулинов. . . .
Ломающие изменения в C#.NStar Alpha
Etyuhibosecyu 20.11.2025
Уже можно не только тестировать, но и пользоваться C#. NStar - писать оконные приложения, содержащие надписи, кнопки, текстовые поля и даже изображения, например, моя игра "Три в ряд" написана на этом. . .
Мысли в слух
kumehtar 18.11.2025
Кстати, совсем недавно имел разговор на тему медитаций с людьми. И обнаружил, что они вообще не понимают что такое медитация и зачем она нужна. Самые базовые вещи. Для них это - когда просто люди. . .
Создание Single Page Application на фреймах
krapotkin 16.11.2025
Статья исключительно для начинающих. Подходы оригинальностью не блещут. В век Веб все очень привыкли к дизайну Single-Page-Application . Быстренько разберем подход "на фреймах". Мы делаем одну. . .
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2025, CyberForum.ru