Палиндром, организация проверки
Добрый день. Каким образом можно сделать обработку числа на палиндром? Задание следующее: необходимо найти максимальный палиндром путем умножения двух пятизначных простых чисел. Используя решето Эратосфена нашел массив простых чисел, потом отфильтровал по заданному диапазону и перевернул массив, далее хотел пройтись циклом для переумножения чисел и проверки на палиндром, но как быть с проверкой: число приравненное к функции отдает ложь?
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>
|
Gtfuc,
замените www функцию на своё |
Цитата:
|
35
var arr = www(),
36
a = {r:0};
37
for (var i=0; i<arr.length; i++) {
38
for (var j=i; j<arr.length; j++) {
39
var n = arr[i] * arr[j];
40
if(n > a.r && palindrome(n)) {a.r = n; a.a = arr[i], a.b = arr[j] }
41
}
42
}
Можете объяснить проверку и работу с массивом через a{}? Возможно прикрутить к моему алгоритму? Запускал ваш код - 7 секунд:victory: |
Gtfuc,
что тут обьяснять не понимаю -- если результат умножения больше эталона и является полиндромом --- меняем эталон на новый от вашего 2 строки отличие |
Gtfuc,
<!DOCTYPE html>
<html>
<head>
<title>title</title>
</head>
<body> <p></p>
<script>
function sieve(n){
console.time("t")
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;
}
var a =[0];
for (i=0; i<rev.length; i++){
for (j=i; j<rev.length; j++){
otv = rev[i]*rev[j];
if(a[0]< otv && palindrome(otv) ){
a =[otv, rev[i], rev[j]]
}
/*else {
document.write("0");
}*/
}
}
console.timeEnd("t")
document.write(a);
}
sieve(100000);
</script>
</body>
</html>
|
рони,
можно ещё ускорить, если помочь браузеру с типами - у меня в хроме за 2 секунды выполняет:
<!DOCTYPE html>
<html>
<head>
<title>title</title>
</head>
<body> <p></p>
<script>
function sieve(n){
console.time("t")
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 = 0|0;
function palindrome(num) {
num = num|0;
var tmp = +num, res = 0|0, dig = 0|0;
while (tmp) {
dig = tmp % 10;
res = res * 10 + dig;
tmp = (tmp - dig) / 10;
}
return res == num;
}
var a =[0];
for (i=0; i<rev.length; i++){
for (j=i; j<rev.length; j++){
otv = rev[i]*rev[j];
if(a[0]< otv && palindrome(otv) ){
a =[otv, rev[i], rev[j]]
}
/*else {
document.write("0");
}*/
}
}
console.timeEnd("t")
document.write(a);
}
sieve(100000);
</script>
</body>
</html>
|
Белый шум, спасибо, вот только результат не является палиндромом.
рони, спасибо, суть сравнения я понимаю. Я имел такой вывод: {a.r = n; a.a = arr[i], a.b = arr[j] } До этого в js не встречал, очень базовые вещи только знаю. |
Цитата:
|
| Часовой пояс GMT +3, время: 08:19. |