Javascript.RU

Создать новую тему Ответ
 
Опции темы Искать в теме
  #1 (permalink)  
Старый 22.08.2017, 20:24
Новичок на форуме
Отправить личное сообщение для Gtfuc Посмотреть профиль Найти все сообщения от Gtfuc
 
Регистрация: 22.08.2017
Сообщений: 7

Палиндром, организация проверки
Добрый день. Каким образом можно сделать обработку числа на палиндром? Задание следующее: необходимо найти максимальный палиндром путем умножения двух пятизначных простых чисел. Используя решето Эратосфена нашел массив простых чисел, потом отфильтровал по заданному диапазону и перевернул массив, далее хотел пройтись циклом для переумножения чисел и проверки на палиндром, но как быть с проверкой: число приравненное к функции отдает ложь?
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
Аватар для рони
Профессор
Отправить личное сообщение для рони Посмотреть профиль Найти все сообщения от рони
 
Регистрация: 27.05.2010
Сообщений: 20,823

Gtfuc,
{"r":999949999,"a":33211,"b":30109}
Ответить с цитированием
  #3 (permalink)  
Старый 22.08.2017, 21:44
Аватар для рони
Профессор
Отправить личное сообщение для рони Посмотреть профиль Найти все сообщения от рони
 
Регистрация: 27.05.2010
Сообщений: 20,823

Gtfuc,
Сообщение от Gtfuc
пятизначных простых чисел
всего таких чисел 8403
8403 * 8403 = 70610409 не всякий браузер выдержит проверку такого количества чисел, нужна хорошая оптимизация
Ответить с цитированием
  #4 (permalink)  
Старый 22.08.2017, 22:23
Новичок на форуме
Отправить личное сообщение для Gtfuc Посмотреть профиль Найти все сообщения от Gtfuc
 
Регистрация: 22.08.2017
Сообщений: 7

рони,
я понимаю, что простых чисел 8к на 8к, но это я и до этого знал. Я спрашиваю как оптимизировать?
Ответить с цитированием
  #5 (permalink)  
Старый 22.08.2017, 22:34
Аватар для рони
Профессор
Отправить личное сообщение для рони Посмотреть профиль Найти все сообщения от рони
 
Регистрация: 27.05.2010
Сообщений: 20,823

Сообщение от Gtfuc
Я спрашиваю как оптимизировать?
можно половину чисел не проверять, но это мало что изменит.
Ответить с цитированием
  #6 (permalink)  
Старый 22.08.2017, 22:39
Новичок на форуме
Отправить личное сообщение для Gtfuc Посмотреть профиль Найти все сообщения от Gtfuc
 
Регистрация: 22.08.2017
Сообщений: 7

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);
Наколдовал так, что за минуту вывел все палиндромы, аж сам удивился)
Ответить с цитированием
  #7 (permalink)  
Старый 23.08.2017, 00:54
Новичок на форуме
Отправить личное сообщение для Gtfuc Посмотреть профиль Найти все сообщения от Gtfuc
 
Регистрация: 22.08.2017
Сообщений: 7

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

Последний раз редактировалось Gtfuc, 23.08.2017 в 00:56.
Ответить с цитированием
  #8 (permalink)  
Старый 23.08.2017, 01:06
Аватар для рони
Профессор
Отправить личное сообщение для рони Посмотреть профиль Найти все сообщения от рони
 
Регистрация: 27.05.2010
Сообщений: 20,823

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

Последний раз редактировалось рони, 23.08.2017 в 01:24.
Ответить с цитированием
  #9 (permalink)  
Старый 23.08.2017, 01:14
Новичок на форуме
Отправить личное сообщение для Gtfuc Посмотреть профиль Найти все сообщения от Gtfuc
 
Регистрация: 22.08.2017
Сообщений: 7

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

Последний раз редактировалось Gtfuc, 23.08.2017 в 01:18.
Ответить с цитированием
  #10 (permalink)  
Старый 23.08.2017, 01:15
Аватар для рони
Профессор
Отправить личное сообщение для рони Посмотреть профиль Найти все сообщения от рони
 
Регистрация: 27.05.2010
Сообщений: 20,823

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>

Последний раз редактировалось рони, 23.08.2017 в 02:01.
Ответить с цитированием
Ответ



Опции темы Искать в теме
Искать в теме:

Расширенный поиск


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Объединить три конструкции проверки полей в одну golopogos Элементы интерфейса 0 27.01.2015 09:04
Не работает скрипт проверки полей bbmm Общие вопросы Javascript 2 05.08.2014 23:57
Замена запятой на точки для проверки цифр с дробью Telnet Общие вопросы Javascript 7 22.07.2013 10:33
вопрос по алгоритму проверки (для игры) cyber Общие вопросы Javascript 10 10.11.2012 23:15
Результаты проверки сервером формы ekkl jQuery 3 30.01.2010 13:29