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

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

08.11.2018, 16:15. Показов 602. Ответов 5
Метки нет (Все метки)

Author24 — интернет-сервис помощи студентам
Ребят, вот столкнулся с задачей написать небольшой код по нахождению наибольшего числа-палиндрома из определенного диапазона произведения простых пятизначных сомножителей. Работает корректно, но чертовски долго, что, в принципе и логично, ведь количество итераций из-за заданного диапазона весьма внушающее. Функция проверки на простоту максимально быстрая, на палиндром в целом никаких ресурсов и не кушает, вопрос конкретно в умножении всех (простых!)множителей.
Может кто посоветовать как это дело ускорить?

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
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
08.11.2018, 16:15
Ответы с готовыми решениями:

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

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

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

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

5
112 / 91 / 31
Регистрация: 24.10.2018
Сообщений: 336
08.11.2018, 16:27 2
Как минимум, можно итерировать через 1, так как все четные числа сразу можно игнорировать, они 100% не простые. Вложенный цикл не понятно, зачем начинать с 99999, числа от i до 99999 и так уже пройдены и проверены во внешнем цикле.
0
0 / 0 / 0
Регистрация: 08.11.2018
Сообщений: 3
08.11.2018, 19:12  [ТС] 3
По поводу итерации через единицу информация полезная, неплохо сократит время.
По поводу вложенного цикла :
Нужны комбинации всех произведений i*j, чтобы найти максимальный палиндром.
0
112 / 91 / 31
Регистрация: 24.10.2018
Сообщений: 336
09.11.2018, 15:22 4
Цитата Сообщение от 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  [ТС] 5
Справедливое замечание, ведь действительно так и выходит.
Хмм, а как от этого избавиться?
Разделить диапазон на две половины и в каждый цикл по половине запихнуть?
0
112 / 91 / 31
Регистрация: 24.10.2018
Сообщений: 336
09.11.2018, 16:34 6
Цитата Сообщение от quazzy Посмотреть сообщение
Хмм, а как от этого избавиться?
Просто начинать не с 99999 вложенный цикл, а с i.
0
09.11.2018, 16:34
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
09.11.2018, 16:34
Помогаю со студенческими работами здесь

Нужен совет по оптимизации
Заранее благодарен за любой дельный совет! Подскажите как можно оптимизировать этот сайт...

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

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

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


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

Или воспользуйтесь поиском по форуму:
6
Ответ Создать тему
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2024, CyberForum.ru