需要帮助解决欧拉计划问题200 [英] Need help solving Project Euler problem 200

问题描述

我正在尝试制定一种算法来解决 Project Euler's Problem 200 .

I am trying to formulate an algorithm to solve Project Euler's Problem 200.

我们将一个sqube定义为一个数字 形式为 p ² q ³ ，其中 p 和 q 是 不同的素数.例如200 = 5 ² 2 ³ 或120072949 = 23 ² 61 ³ .

We shall define a sqube to be a number of the form, p²q³, where p and q are distinct primes. For example, 200 = 5²2³ or 120072949 = 23²61³.

前五个sqube是72、108， 200、392和500.

The first five squbes are 72, 108, 200, 392, and 500.

有趣的是，第200个也是 您无法更改的号码 一位数作质数；我们应该 称此类数字为素数.这 下一个防渗漏的乌贼，其中包含 连续子字符串"200"为 1992008.

Interestingly, 200 is also the first number for which you cannot change any single digit to make a prime; we shall call such numbers, prime-proof. The next prime-proof sqube which contains the contiguous sub-string "200" is 1992008.

找到第200个防渗漏的乌贼 包含连续的子字符串 "200".

Find the 200th prime-proof sqube containing the contiguous sub-string "200".

有人可以指出正确的方向来帮助我解决这个问题吗?

Can someone please point me in the right direction to help me solve this problem?

推荐答案

我不确定这是一个很好的SO问题，但这至少可以帮助您入门.

I'm not sure this is a great SO question, but this should get you started at least.

从算法上讲，蛮力和无知的方法应该非常简单:

Algorithmically, the brute force and ignorance approach to this should be pretty straightforward:

1. 以素数集P开头
2. 通过查看P中所有带有p1，p2的有序对(p1，p2)来生成"squbes"
3. 订购此列表，将其称为集合S(想想:如何在生成它们的同时执行此操作)
4. 依次测试S中的每个，查找子字符串200
5. 如果s包含"200"，请测试s的每个一位数字修改是否为质数
6. 如果它们都不是素数，则您已经找到了防素的sqube.将其放入列表中，找到第200个列表即可.

现在，这里更有趣的事情是看看您是否可以做一些少一些的蛮力和无知之举.首先，以上方法是否可行(假设进行快速的素数测试)?很容易估算出sqube增长的速度，但是对于防噪的sqube或包含200的sqube来说并没有那么快.您能看到任何快捷方式吗?

Now the more interesting thing here is to see if you can do something a bit less brute force and ignorance. First off, is the above even practical (assuming a fast primality test)? Easy enough to estimate how fast the squbes grow, but not so much with the prime-proof ones, or the ones containing 200. Can you see any shortcuts?

玩得开心！

这篇关于需要帮助解决欧拉计划问题200的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！