Форум

Gtfuc · #1 (**permalink**) 22.08.2017, 20:24

Добрый день. Каким образом можно сделать обработку числа на палиндром? Задание следующее: необходимо найти максимальный палиндром путем умножения двух пятизначных простых чисел. Используя решето Эратосфена нашел массив простых чисел, потом отфильтровал по заданному диапазону и перевернул массив, далее хотел пройтись циклом для переумножения чисел и проверки на палиндром, но как быть с проверкой: число приравненное к функции отдает ложь?

function sieve(n){
		S=[];
		S[1]=0;
		for(k=2;k<=n; k++)
			S[k]=k;
		for(k=2;k*k<=n; k++){
			if(S[k]==k){
				for(l=k*k; l<=n; l+=k){
					S[l]=0;
				}
			}
		}
		var filterS = S.filter(function(filt){
			return filt!=0 && filt>10000;
		});
		var rev = filterS.reverse();
		var otv;
                function pal(n){
		var obr = 0;
		while (n>0){
			obr = 10* obr + n%10;
			n/=10;
		}
		return obr;
	}
		for (i=0; i<1000; i++){
			for (j=0; j<1000; j++){
				otv = rev[i]*rev[j];
				if(otv == pal(otv))
				document.write(otv+" ");
			}
		}
	}
	sieve(100000);

рони · #2 (**permalink**) 22.08.2017, 21:39

Gtfuc,

{"r":999949999,"a":33211,"b":30109}

рони · #3 (**permalink**) 22.08.2017, 21:44

Gtfuc,

Сообщение от Gtfuc

пятизначных простых чисел

всего таких чисел 8403
8403 * 8403 = 70610409 не всякий браузер выдержит проверку такого количества чисел, нужна хорошая оптимизация

Gtfuc · #4 (**permalink**) 22.08.2017, 22:23

рони,
я понимаю, что простых чисел 8к на 8к, но это я и до этого знал. Я спрашиваю как оптимизировать?

рони · #5 (**permalink**) 22.08.2017, 22:34

Сообщение от Gtfuc

Я спрашиваю как оптимизировать?

можно половину чисел не проверять, но это мало что изменит.

Gtfuc · #6 (**permalink**) 22.08.2017, 22:39

function sieve(n){
		S=[];
		S[1]=0;
		for(k=2;k<=n; k++)
			S[k]=k;
		for(k=2;k*k<=n; k++){
			if(S[k]==k){
				for(l=k*k; l<=n; l+=k){
					S[l]=0;
				}
			}
		}
		var filterS = S.filter(function(filt){
			return filt!=0 && filt>10000;
		});
		var rev = filterS.reverse();
		var otv;
		
		function palindrome(num) {
    	var tmp = num, res = 0, dig;
    	while (tmp) {
        dig = tmp % 10;
        res = res * 10 + dig;
        tmp = (tmp - dig) / 10;
    	}
    	return res == num;
		}

		for (i=0; i<rev.length; i++){
			for (j=0; j<rev.length; j++){
				otv = rev[i]*rev[j];
				if(palindrome(otv)){
					document.write(otv+" ");
				}
				/*else {
					document.write("0");
				}*/
			}
		}
	}
	sieve(100000);

Наколдовал так, что за минуту вывел все палиндромы, аж сам удивился)

Gtfuc · #7 (**permalink**) 23.08.2017, 00:54

рони,
Код обрабатывает 8к X 8к за 22 секунды, что для меня хорошо, в отличие от того, что было на первом этапе. Возник вопрос как вывести максимальный элемент и сомножители? снова запуливать значения в массив, потом перебирать и выводить максимальный? Подскажите ход действий? Интересует также ваш вариант оптимизации, хотя бы на словах?

рони · #8 (**permalink**) 23.08.2017, 01:06

Gtfuc,
ваш алгоритм поиска простых чисел пропустил
10201,10609,11449,11881,12769,16129,17161,18769,19 321,22201,22801,24649,26569,27889,29929,32041,3276 1,36481,37249,38809,39601,44521,49729,51529,52441, 54289,57121,58081,63001,66049,69169,72361,73441,76 729,78961,80089,85849,94249,96721,97969

и строка 30
for (j=0; заменить на for (j=i; так половину чисел не надо будет проверять, потому что 4*9 == 9*4

Gtfuc · #9 (**permalink**) 23.08.2017, 01:14

рони,
10201 не простое число 101X101= 10201, 103X103=10609 и т.д. - ваш алгоритм работает неправильно. за цикл спасибо, действительно не имеет смысл проверять числа( еще со школы от перемены мест слагаемых сумма не меняется). По поводу поиска максимального палиндрома, как лучше реализовать? Сократили время выполнения вдвое(11 секунд).

рони · #10 (**permalink**) 23.08.2017, 01:15

Gtfuc,

<!DOCTYPE html>

<html>
<head>
  <title>title</title>

</head>

<body> <p></p>
<script>

function www() { //поиск всех 5-значных простых чисел
var p = 100000,j = 10000,
    h = [];
    for (; j <= p; j++) {
       var k = 0, n = Math.sqrt(j);
        for (var i = 2; i <= n; i++)
            if (j % i == 0) k = k + 1;
        k || h.push(j)
    }
    return h
};

function palindrome(num) {
    	var tmp = num, res = 0, dig;
    	while (tmp) {
        dig = tmp % 10;
        res = res * 10 + dig;
        tmp = (tmp - dig) / 10;
    	}
    	return res == num;
    }

console.time("t")
var arr = www(),
a = {r:0};
for (var i=0; i<arr.length; i++)  {
for (var j=i; j<arr.length; j++)  {
var n = arr[i] * arr[j];
if(n < a.r)  continue;
if(palindrome(n))  {a.r = n; a.a = arr[i];a.b = arr[j] }
}
}
console.timeEnd("t")
document.querySelector("p").innerHTML = JSON.stringify(a);
  </script>
</body>
</html>

Форум

Справочник

Discord чат

Курсы javascript