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

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

08.11.2018, 16:15. Показов 716. Ответов 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
Ответ Создать тему
Новые блоги и статьи
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