题目4：找出由两个三位数乘积构成的回文

learner-ray

i初始化为2*3*5*7*11*13*17*19是抄的评论大神的，我自己写的是i初始化为21，循环i++;运行了2秒多。大神的方法只运行了0.2秒。快了十倍。
结果：最小能被1-20 中每个数整除的正整数是232792560

#include<stdio.h>

int main(void)
{
        int i, k, j;
        int count;
        i = k = 2*3*5*7*11*13*17*19;
        
        while (1)
        {
                count = 0;
                for (j = 1; j < 21; j++)
                {
                        if (i % j == 0)
                        {
                                count++;
                        }
                        else
                        {
                                break;
                        }
                }
                if (count == 20)
                {
                        printf("最小能被1-20 中每个数整除的正整数是%d\n", i);
                        break;
                }
                else
                {
                        i = i + k;
                }
        }
        return 0;
}

guosl

/*
找出由两个3位数相乘得到的最大回文乘积。
答案：906609
耗时：0.00836184秒（单线程）
      0.00248691秒（八线程）
*/
#include <iostream>
#include <algorithm>
#include <omp.h>
using namespace std;

inline bool ChkPalindrome(int k)
{
  int x = k, y = 0;
  while (x > 0)
  {
    y = 10 * y + x % 10;
    x = x / 10;
  }
  return (y == k);
}

int main(void)
{
  double t = omp_get_wtime();
  int x = 0;
#pragma omp parallel for reduction(max:x)
  for (int i = 100; i <= 999; ++i)
  {
    for (int j = i; j >= 100; --j)
    {
      int a = i * j;
      if (ChkPalindrome(a))
      {
        x = max(x, a);
        break;
      }
    }
  }
  t = omp_get_wtime() - t;
  cout << x << endl << "耗时：" << t << "秒" << endl;
  return 0;
}

mathtimes

#include <cstdio>
bool isPalindromicNumber(int num)
{
    char bits[6] = {0};
    int len = 0;
    for(;num>0;len++)
    {
        bits[len] = num%10;
        num /= 10;
    }
    for(int i=0;i<len/2+1;i++)
        if(bits[i]!=bits[len-i-1])
            return false;
    return true;
}
int main()
{
    int max = 0;
    for(int i=100;i<1000;i++)
        for(int j=100;j<1000;j++)
            if(isPalindromicNumber(i*j)&&i*j>max)
                max =i*j;
    printf("%d",max);
}

jerryxjr1220

package main

import (
        "fmt"
        "time"
)

//题目4：
//
//一个回文数指的是从左向右和从右向左读都一样的数字。最大的由两个两位数乘积构成的回文数是 9009 = 91 * 99。
//
//找出最大的有由个三位数乘积构成的回文数。
func main() {
        t := time.Now()
        var nums [10000]int
        index := 0
        for a := 100; a < 1000; a++ {
                for b := 100; b < 1000; b++ {
                        c := a * b
                        str := fmt.Sprintf("%d", c)
                        flag := true
                        length := len(str) - 1
                        for i := 0; i < length; i++ {
                                if str[i] != str[length-i] {
                                        flag = false
                                        break
                                }
                        }
                        if flag {
                                nums[index] = c
                                index++
                        }
                }
        }
        max := 0
        for i := 0; i < len(nums); i++ {
                if nums[i] > max {
                        max = nums[i]
                }
        }
        fmt.Println(max)
        tt := time.Now()
        fmt.Println("耗时：", (tt.Nanosecond()-t.Nanosecond())/1e6, "ms")
}

输出：

GOROOT=C:\Program Files\Go #gosetup
GOPATH=C:\Users\Administrator\go #gosetup
"C:\Program Files\Go\bin\go.exe" build -o C:\Users\Administrator\AppData\Local\Temp\GoLand\___10go_build_GoProject_src.exe C:\Users\Administrator\Documents\GoProject\src\Euler04.go #gosetup
C:\Users\Administrator\AppData\Local\Temp\GoLand\___10go_build_GoProject_src.exe
906609 
耗时： 47 ms 

进程 已完成，退出代码为 0

B1tetheDust

import time


def is_palindrome(num):
    str_num = str(num)
    if str_num == str_num[::-1]:
        return True
    return False


start = time.perf_counter()
print(max([i*j for i in range(999, 99, -1) for j in range(i, 99, -1) if is_palindrome(i*j)]))
end = time.perf_counter()
print('It takes %f s' % (end - start))

清风揽月shine

import time


def palindrome_data(power):
    """
    : 由几位数构成的回文
    :param power:
    :return:
    """
    st = time.time()
    start = 10 ** (power - 1)
    end = 10 ** power
    all_palin_data = []
    t = 0
    x = 0
    y = 0
    for i in range(end, start, -1):  # 这里反着取效率最高
        for j in range(end, start, -1):
            result = i * j

            if str(result) == str(result)[::-1]:
                if result > t:
                    t = result # 保存变量占用内存就会浪费时间
                    x = i
                    y = j
                ele = (x, y, t)
                if ele not in all_palin_data:
                    all_palin_data.append((x, y, t))
                break  # 这里取到一个最大的就不用继续在这个循环里面浪费时间了

    print(all_palin_data)
    print('用时%.5f' % (time.time() - st))

开飞机的羊驼

num = 13195
list = []
list1 = []
#先用for循环寻找所有的因子并存储list
for i in range(1, num):
    if num % i == 0:
        list.append(i)
print(list)
# 用两个for循环来判断list中的因子那些是质数
for j in list:
    if (j != 1) and (j != num):
        for k in range(2, j):
            if j % k == 0 :
                break
        else:
            list1.append(j)
print(list1)
print("最大质数因子为%d"%list1[-1])

Asss-whom

pub fn run() -> Result<(), Box<dyn std::error::Error>> {
    let num = (100..1000)
        .filter_map(|x| {
            (100..1000)
                .map(|y| x * y)
                .filter(|x| x.to_string().chars().rev().collect::<String>() == x.to_string())
                .max()
        })
        .max();
    println!("{:?}", num);
    Ok(())
}

[Euler Project 4]
Some(906609)
[Task finished in 0.1414863s]

_乏趣味

z=1
for m in range(999999,1,-1):
        if str(m)==str(m)[::-1] and z:
                for k in range(int(m**0.5),1,-1):
                        if 99<k<1000 and 99<m/k<1000 and m%k==0:
                                re=[m,k,int(m/k)]
                                z=0
                                print(re)

Eca

#include <stdio.h>

int cmp(int n) {
        int ax = n / 1000;
        int tmpa = 0, tmpb = 0, max = 100;
        while (ax > 0) {
                tmpa += (ax % 10) * max;
                max /= 10;
                ax /= 10;
        }

        max = 100;
        ax = tmpa;
        while (ax > 0) {
                tmpb += (ax % 10) * max;
                max /= 10;
                ax /= 10;
        }
        if (tmpb * 1000 + tmpa == n)
                return 1;
        else
                return 0;

}



int main() {
        for (int i = 999999;; i--) {
                if (cmp(i)) {
                        for (int j = 999;; j--) {
                                int t1 = i / j;
                                float t2 = (float)i / (float)j;
                                if ((float)t1 == t2 && t1 < 1000 && t2 < 1000 ) {
                                        printf("%d\n", i);
                                        return 0;
                                } else if (t1 > 1000 || t2 > 1000)
                                        break;
                                else
                                        continue;
                        }
                } else
                        continue;
        }
        return 0;
}

qingyunvi

import time

start = time.time()
muli = 0
num_dict = {}
for i in range(100, 1000):
    for j in range(100, 1000):
        muli = i * j
        if str(muli) == str(muli)[::-1]:
            output = "%s = %d * %d" % (muli, i, j)
            num_dict.setdefault(muli, output)
            # print("%s = %d * %d" % (muli, i, j))

keys = num_dict.keys()
max_key = max(keys)
print(num_dict[max_key])
end = time.time()
print("time: %s" % (end - start))

906609 = 913 * 993
time: 0.5153927803039551
感觉速度算是比较慢的，应该是嵌套了循环有关

Ian_Li

无名侠 发表于 2015-7-9 14:41
难点应该就是判断是否为回文了。
我用的方法有些歪门邪道，利用字符串来判断，不过效率还行。
然后就是三 ...

为什么 第一层循环从500向下递减？也应该从999开始呀

Ian_Li

c++练习，day4

i:993,j:913,product:906609

#include <iostream>
using namespace std;

// 翻转数字比较
int isPalindrome(int n) {
    int t = n;
    int rn = 0;
    while (t != 0) {
        rn = 10 * rn + t % 10;
        t /= 10;
    }
    if (rn != n) return 0;
    return 1;
}
// 转字符串比对字符
int isPalindrome_2(int n) {
    string sn = to_string(n);
    int len = sn.length();
    for (int i = 0; i < len / 2; i++) {
        if (sn[i] != sn[len - i - 1]) return 0;
    }
    return 1;
}

int main() {
    int max_j = 0;
    int max_product = 0;
    int ir;
    int jr;
    for (int i = 999; i > 99; i--) {
        if (i == max_j) break; // 剪枝
        for (int j = i; j > 99; j--) {
            int product = i * j;
            if (isPalindrome_2(product)) {
                if (j > max_j) max_j = j;
                if (product > max_product) {
                    max_product = product;
                    ir = i;
                    jr = j;
                    break;
                }
            }
        }
    }
    cout << "i:" << ir << ",j:" << jr << ",product:" << max_product << endl;
}