Project Euler 4 Coding with a new approach fails.

The number of palindromes that have the same value when read from either the left or right is called the number of palindromes. Of the number of palindromes represented by the product of two-digit numbers, the maximum is 9009 = 91 x 99.

Now, find the maximum number of palindromes represented by the product of three-digit numbers. http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%204

I reviewed the code I wrote. It seems that there is room for improvement in terms of primality test, because it is judged whether or not the remainder of division becomes 0.

pe4.png

The following algorithm was considered as an algorithm similar to the Eratostenes sieve.

  1. First, make a list of numbers that is the product of three-digit numbers. [False, False, ‥, True, ‥] Corresponding to each number less than 1 million, where True is the product of 3 digit numbers
  2. Generate the number of palindromes with target = seed * 1000 + int (str (seed) [:: -1]), search the above list from the largest number, and finish when the number that becomes True is found.

I implemented the above.

def erat_approach():
  tl = [False]*(10**6)
  for i in range(800,1000):
    tl[i*800:i*1000:i] = [True]*200
  t = 999
  while 1:
    n = t*1000+int(str(t)[::-1])
    if tl[n]:
      break
    t-=1
  print n

Result: Explosion was late (executed 100 times)

pe4_2.png

Recommended Posts

Project Euler 4 Coding with a new approach fails.
Project Euler 37
Project Euler 7
Project Euler 47
Project Euler 4
Create a new Python numerical calculation project
Project Euler 38
Project Euler 17
Project Euler 26
Project Euler 8
Project Euler 23
Project Euler 22
Project Euler 19
Project Euler 50
Project Euler 42
Project Euler 33
Project Euler 43
Project Euler 35
Project Euler 36
Project Euler 24
Project Euler 46
Project Euler 48
Project Euler 45
Project Euler 6
Project Euler 44
Project Euler 39
Project Euler 40
Project Euler 49
Project Euler 29
Project Euler 27
Project Euler 41
Project Euler 18
Project Euler 13
Project Euler 30
Project Euler 16
Project Euler 14
Project Euler 34
Project Euler 25
Create a new page in confluence with Python
[Project Euler] problem1
Tasks at the start of a new python project
Current directory when creating a new one with Jupyter
I can't exe a project using PyWebView with PyInstaller