1 / 1 / 0
Регистрация: 25.11.2017
Сообщений: 17
1

Найти минимальное простое число-палиндром не меньше заданного N

29.11.2018, 10:59. Показов 2200. Ответов 4
Метки math (Все метки)

Понятие простой - делится на себя и на 1. Понятие палиндром - читается одинаково с одних и тех же сторон (121,70207 и тд).
Написать программу которая находит минимальное простое число палиндром не меньше заданного N. Границы числа N (1<=N<=10^6).
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
#include "stdafx.h"
#include<iostream>
using namespace std;
 
int main()
{
    long int n, digit, rev = 0, temp = 0, total = 0;
    cin >> n;
    if (n <= 1000000 && 1 <= n) {
        for (int i = n + 1; i <= 1000000; ++i) {
            for (int j = 1; j <= i; ++j) {
                if (i%j == 0) {
                    ++total;
                    if (total > 2) {
                        j = i+1;
                    }
                }
            }
            if (total == 2) {
                temp = i;                                       
                while (temp != 0) {                             
                    digit = temp % 10;
                    rev = (rev * 10) + digit;
                    temp = temp / 10;
                }
                if (rev == i) {
                    cout << "Yes:" << i << endl;
                    system("pause");
                    return 0;
                }
                
                rev = 0;
            }
            total = 0;      
        }
    }
    else {
        cout << "Num is so big " << endl;
        system("pause");
        return 1;
    }
    cout << "this num does not exist";
    system("pause");
    return 0;
}
Этот говно код работает только с маленькими цифрами, 10^5 уже не осиливает. Подскажите где можно упростить задачу циклу.
__________________
Помощь в написании контрольных, курсовых и дипломных работ, диссертаций здесь
0
Лучшие ответы (1)
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
29.11.2018, 10:59
Ответы с готовыми решениями:

Найти минимальное простое число палиндром не меньше заданного числа N
Назовем натуральное число палиндромом, если оно не меняется при перестановке его цифр в обратном...

Определить ближайшее простое число, меньше заданного
определить просто число меньше заданного(просто то которое делится на 1 и на самого себя и только)...

В массиве из целых чисел найти минимальное простое число
Вообщем задача звучит так: &quot;В массиве из целых чисел найти минимальное простое число.&quot; Все что я...

Передать в функцию целое число. Функция заменяет его на ближайшее простое число, которое больше или меньше исходного. Вернуться в main( ) и распечатат
Передать в функцию целое число. Функция заменяет его на ближайшее простое число, которое больше или...

4
1269 / 1026 / 470
Регистрация: 25.12.2016
Сообщений: 3,333
29.11.2018, 13:42 2
Лучший ответ Сообщение было отмечено Mark5 как решение

Решение

Цитата Сообщение от Mark5 Посмотреть сообщение
Подскажите где можно упростить задачу циклу.
Во-первых, проверять сначала на палиндромность, а только потом на простоту.

Во-вторых, проверку числа на простоту можно существенно ускорить: если найден хотя бы один делитель, то число уже не простое и цикл можно завершить. Кроме того, можно проверять только нечётные делители, и не до i, а до sqrt(i). Так будет гораздо быстрее. Если нужно, на форуме легко найти готовую реализацию этого алгоритма.
1
1 / 1 / 0
Регистрация: 25.11.2017
Сообщений: 17
29.11.2018, 18:45  [ТС] 3
Цитата Сообщение от likehood Посмотреть сообщение
Во-первых, проверять сначала на палиндромность, а только потом на простоту.

Во-вторых, проверку числа на простоту можно существенно ускорить: если найден хотя бы один делитель, то число уже не простое и цикл можно завершить. Кроме того, можно проверять только нечётные делители, и не до i, а до sqrt(i). Так будет гораздо быстрее. Если нужно, на форуме легко найти готовую реализацию этого алгоритма.
Спасибо, я вот только одно не могу понять как корень числа облегчает процесс?
0
1269 / 1026 / 470
Регистрация: 25.12.2016
Сообщений: 3,333
29.11.2018, 19:23 4
Цитата Сообщение от Mark5 Посмотреть сообщение
я вот только одно не могу понять как корень числа облегчает процесс?
Как быстрее перебирать делители: от 2 до 10000 или от 2 до 100?

Понятно, что до 100. И этого вполне достаточно, остальные делители перебирать не нужно.
0
Модератор
Эксперт функциональных языков программированияЭксперт Python
32449 / 17991 / 3765
Регистрация: 12.02.2012
Сообщений: 30,188
Записей в блоге: 5
29.11.2018, 19:51 5
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
#include <cstdlib>
#include <iostream>
 
using namespace std;
 
int isPal(long int n)
{
    long int r=0;
    long int m=n;
    while(m>0)
    {
       r=r*10+m%10;
       m/=10;
    }
    return (r==n);
}       
int isPrime(long int n)
{
    if (n==1) return 0;
    if (n<=3) return 1;
    if (n%2==0) return 0;
    for (long int i=3; i<=n/2; i+=2) if (n%i==0) return 0;
    return 1;
}    
int main(int argc, char *argv[])
{
    long int N;
    cout << "N=";
    cin >> N;
    while(1)
    {
       if (isPal(N))
       {
          if (isPrime(N)) 
          {          
             cout << N <<endl;
             break;
          }   
       }
       N++;
    }          
    system("PAUSE");
    return EXIT_SUCCESS;
}
0
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
29.11.2018, 19:51
Помогаю со студенческими работами здесь

Определить ближайшее простое число, большее заданного
Определить ближайшее простое число,больше заданного с++

Найти следующий палиндром после заданного
Здравствуйте. Есть вот такое задание: На одометре (прибор для измерения пробега автомобиля)...

Найти P наибольшее простое число, меньшее заданного T
Найти P наибольшее простое число, меньшее заданного T

Найти первое простое число, больше заданного n
Напишите, пожалуйста программу: Найти первое простое число, больше заданного n


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

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

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2022, CyberForum.ru