Форум программистов, компьютерный форум, киберфорум
Visual C++
Войти
Регистрация
Восстановить пароль
Блоги Сообщество Поиск Заказать работу  
 
Рейтинг 5.00/3: Рейтинг темы: голосов - 3, средняя оценка - 5.00
0 / 0 / 0
Регистрация: 08.11.2018
Сообщений: 3

Нужен совет по оптимизации кода

08.11.2018, 16:15. Показов 749. Ответов 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
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
#include "pch.h"
#include <iostream>
 
using namespace std;
 
int isPrime(unsigned long long a);
int isPalindrome(unsigned long long a);
 
int main()
{
    unsigned long long prod = 1,max = 0;
    unsigned long long iI = 0, jJ = 0;
 
    for (unsigned long long i = 99999; i > 10001; --i) {
 
        if (isPrime(i) == 1) {
            for (unsigned long long j = 99999; j > 10001; --j) {
                if (isPrime(j) == 1) {
                    prod = i * j;
                    if (isPalindrome(prod) == 1) {
                        if (max == 0)max = prod;
                        if (max <= prod) {
                            max = prod;
                            iI = i;
                            jJ = j;
                        }
                    }
                }
            }
        }
    }
    
 
 
    if(isPalindrome(max)==1)cout << prod << endl <<  iI << endl << jJ;
    else cout << "\nPalindrome wasn't found";
}
 
 
int isPrime(unsigned long long a) {
    unsigned long i1, i2, i3, i4, i5, i6, i7, i8, bound;
    if (a == 0 || a == 1)
        return 0;
    if (a == 2 || a == 3 || a == 5 || a == 7 || a == 11 || a == 13 || a == 17 || a == 19 || a == 23 || a == 29)
        return 1;
    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 0;
    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 0;
    return 1;
}
 
int isPalindrome(unsigned long long a) {
    unsigned long long temp = a;
 
    unsigned long long reversed = 0;
 
    while (temp != 0)
    {
        reversed = reversed * 10 + temp % 10;
        temp /= 10;
    }
 
    if (a == reversed)
        return 1;
    else
        return 0;
}
0
IT_Exp
Эксперт
34794 / 4073 / 2104
Регистрация: 17.06.2006
Сообщений: 32,602
Блог
08.11.2018, 16:15
Ответы с готовыми решениями:

Нужен совет в оптимизации кода
Нужно оптимизировать метод Deallocate, который переводит нужный указатель из allotted в exempted, и, если указателя нет, бросает ошибку. Я...

Нужен совет по выбору программы или плагина для оптимизации HTML-кода
Посоветуйте какими программами оптимизации вы пользуетесь? Возможно есть плагины для sublime ил atom. Спасибо )

Нужен совет по оптимизации
Последнее время (еще до 20.01.10) яндекс начал выдавать запросы по нерелевантным страницам. Сайт: rvisa.ru На сайте есть 2 колонки -...

5
112 / 91 / 31
Регистрация: 24.10.2018
Сообщений: 336
08.11.2018, 16:27
Как минимум, можно итерировать через 1, так как все четные числа сразу можно игнорировать, они 100% не простые. Вложенный цикл не понятно, зачем начинать с 99999, числа от i до 99999 и так уже пройдены и проверены во внешнем цикле.
0
0 / 0 / 0
Регистрация: 08.11.2018
Сообщений: 3
08.11.2018, 19:12  [ТС]
По поводу итерации через единицу информация полезная, неплохо сократит время.
По поводу вложенного цикла :
Нужны комбинации всех произведений i*j, чтобы найти максимальный палиндром.
0
112 / 91 / 31
Регистрация: 24.10.2018
Сообщений: 336
09.11.2018, 15:22
Цитата Сообщение от quazzy Посмотреть сообщение
Нужны комбинации всех произведений i*j, чтобы найти максимальный палиндром.
Да. И с твоим вариантом циклов, i*j будут выполняться дважды, потому что j пройдет по тем же числам, по которым уже i ходил. В итоге ты выполнишь i*j, а потом еще j*i. И это не только дублирует умножение, но еще и проверку чисел на простоту, которых проверять уже не надо.

Добавлено через 6 минут
Если еще не догоняешь. Представь, для простоты, что у тебя 99999 - простое число и 99997 - простое число. Больше нет простых. Что произойдет? сначала 99999*99999, это понятно. Потом i останется 99999, а j дойдет до 99997. Снова умножение и все дела. Что дальше? Дальше i дойдет до 99997, а j, станет 99999, так как интерация начинается сначала, а не с i. Опять умножение. Итого, мы поимеем:
99999 * 99999
99999 * 99997
99997 * 99999
99997 * 99997
Ничего не смущает?
0
0 / 0 / 0
Регистрация: 08.11.2018
Сообщений: 3
09.11.2018, 15:50  [ТС]
Справедливое замечание, ведь действительно так и выходит.
Хмм, а как от этого избавиться?
Разделить диапазон на две половины и в каждый цикл по половине запихнуть?
0
112 / 91 / 31
Регистрация: 24.10.2018
Сообщений: 336
09.11.2018, 16:34
Цитата Сообщение от quazzy Посмотреть сообщение
Хмм, а как от этого избавиться?
Просто начинать не с 99999 вложенный цикл, а с i.
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
BasicMan
Эксперт
29316 / 5623 / 2384
Регистрация: 17.02.2009
Сообщений: 30,364
Блог
09.11.2018, 16:34
Помогаю со студенческими работами здесь

Нужен совет по оптимизации
Всем доброго времени, На пайтоне писать начал сравнительно недавно. Прошу совета у более опытных разработчиков. #удаление...

Нужен совет по оптимизации
Заранее благодарен за любой дельный совет! Подскажите как можно оптимизировать этот сайт http://armdelrus.narod.ru в Яше медленно...

Нужен совет по поводу оптимизации
Помогите пожалуйста разобраться почему подтормаживает данная программа deleted link 5.18 Запрещено размещать задания и решения в...

Нужен совет новИчку по оптимизации.
В связи с кризисом (пол года тому) пришлось отказаться от услуг ВЭБ компании и заниматься сайтом самому. Как следсвие пэйдж ранг упал с 3...

Нужен совет по оптимизации сайта
Всем привет. Сколько раз раньше видел, что человек задает вопрос типа: «Дайте советы по улучшению сайта» и ему дают ответы типа: «Читай...


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

Или воспользуйтесь поиском по форуму:
6
Ответ Создать тему
Новые блоги и статьи
SDL3 для Desktop (MinGW): Рисуем цветные прямоугольники с помощью рисовальщика SDL3 на Си и C++
8Observer8 17.03.2026
Содержание блога Финальные проекты на Си и на C++: finish-rectangles-sdl3-c. zip finish-rectangles-sdl3-cpp. zip
Символические и жёсткие ссылки в Linux.
algri14 15.03.2026
Существует два типа ссылок — символические и жёсткие. Ссылка в Linux — это запись в каталоге, которая может указывать либо на inode «файла-ИСТОЧНИКА», тогда это будет «жёсткая ссылка» (hard link),. . .
[Owen Logic] Поддержание уровня воды в резервуаре количеством включённых насосов: моделирование и выбор регулятора
ФедосеевПавел 14.03.2026
Поддержание уровня воды в резервуаре количеством включённых насосов: моделирование и выбор регулятора ВВЕДЕНИЕ Выполняя задание на управление насосной группой заполнения резервуара,. . .
делаю науч статью по влиянию грибов на сукцессию
anaschu 13.03.2026
прикрепляю статью
SDL3 для Desktop (MinGW): Создаём пустое окно с нуля для 2D-графики на SDL3, Си и C++
8Observer8 10.03.2026
Содержание блога Финальные проекты на Си и на C++: hello-sdl3-c. zip hello-sdl3-cpp. zip Результат:
Установка CMake и MinGW 13.1 для сборки С и C++ приложений из консоли и из Qt Creator в EXE
8Observer8 10.03.2026
Содержание блога MinGW - это коллекция инструментов для сборки приложений в EXE. CMake - это система сборки приложений. Здесь описаны базовые шаги для старта программирования с помощью CMake и. . .
Как дизайн сайта влияет на конверсию: 7 решений, которые реально повышают заявки
Neotwalker 08.03.2026
Многие до сих пор воспринимают дизайн сайта как “красивую оболочку”. На практике всё иначе: дизайн напрямую влияет на то, оставит человек заявку или уйдёт через несколько секунд. Даже если у вас. . .
Модульная разработка через nuget packages
DevAlt 07.03.2026
Сложившийся в . Net-среде способ разработки чаще всего предполагает монорепозиторий в котором находятся все исходники. При создании нового решения, мы просто добавляем нужные проекты и имеем. . .
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2026, CyberForum.ru