Палиндром, организация проверки
Добрый день. Каким образом можно сделать обработку числа на палиндром? Задание следующее: необходимо найти максимальный палиндром путем умножения двух пятизначных простых чисел. Используя решето Эратосфена нашел массив простых чисел, потом отфильтровал по заданному диапазону и перевернул массив, далее хотел пройтись циклом для переумножения чисел и проверки на палиндром, но как быть с проверкой: число приравненное к функции отдает ложь?
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);
|
Gtfuc,
{"r":999949999,"a":33211,"b":30109}
|
Gtfuc,
Цитата:
8403 * 8403 = 70610409 не всякий браузер выдержит проверку такого количества чисел, нужна хорошая оптимизация |
рони,
я понимаю, что простых чисел 8к на 8к, но это я и до этого знал. Я спрашиваю как оптимизировать? |
Цитата:
|
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);
Наколдовал так, что за минуту вывел все палиндромы, аж сам удивился) |
рони,
Код обрабатывает 8к X 8к за 22 секунды, что для меня хорошо, в отличие от того, что было на первом этапе. Возник вопрос как вывести максимальный элемент и сомножители? снова запуливать значения в массив, потом перебирать и выводить максимальный? Подскажите ход действий? Интересует также ваш вариант оптимизации, хотя бы на словах? |
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 |
рони,
10201 не простое число 101X101= 10201, 103X103=10609 и т.д. - ваш алгоритм работает неправильно. за цикл спасибо, действительно не имеет смысл проверять числа( еще со школы от перемены мест слагаемых сумма не меняется). По поводу поиска максимального палиндрома, как лучше реализовать? Сократили время выполнения вдвое(11 секунд). |
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>
|
| Часовой пояс GMT +3, время: 00:47. |