如何找到帶有四個自由分母的前四個連續數字？

Question

前兩個有兩個免費分母的連續編號：

14 = 2 × 7 
15 = 3 × 5 

前三個連續三個免費分母的數字是：

644 = 2 × 7 × 23 
645 = 3 × 5 × 43 
646 = 2 × 17 × 19 

我怎樣才能找到的第一個連續四個數字與正好四個免費的分母？

Answer 1

在這裏你去：
134043 = 3 x 7 x 13 x 491
134044 = 2 x 23 x 31 x 47
134045 = 5 x 17 x 19 x 83
134046 = 2 x 3 x 11 x 677

Answer 2

它不是的情況是644 = 2×7×23相反644 = 2×2×7×23 - - 您正在查找具有不同的素數因子的數字，這可能會重複。實際上，1309,1310,1311是前3個數字，它們具有3個不同的非重複因子，並且4個連續數字的任何運行將具有4的重複因子，因此不可能這樣做。

爲了解決發現4個連續的數字的每一個具有4個不同的問題（雖然可能重複）的素因子，則可以使用Sieve of Eratosthenes，其中一個保持不同除數的數目的軌道的一個修改的版本：

Function SieveK(n As Long, k As Long) As Long 
    'Implements a modified Sieve of Erasthones 
    'to return the first of k successive numbers 
    'less than or equal to n, each of which has 
    'k distinct prime factors. 
    'Returns -1 if no such number exists 

    Dim nums As Variant 
    Dim i As Long, p As Long 
    Dim run As Long 
    Dim limit As Long 
    Dim primes As Variant 

    primes = Array(2, 3, 5, 7, 11, 13) 'small primes 
    p = 1 
    For i = 0 To k - 2 
     p = p * primes(i) 
    Next i 
    limit = Int(1 + n/p) 

    ReDim nums(2 To n) As Long 
    p = 2 'first prime 
    Do While p < limit 
     'mark subsequent multiples of p by adding 1 
     For i = 2 * p To n Step p 
      nums(i) = nums(i) + 1 
     Next i 
     'find next p -- which will be next 0 
     p = p + 1 
     Do While nums(p) <> 0 
      p = p + 1 
     Loop 
    Loop 
    'At this stage, all numbers are marked. 
    'primes are marked by 0 and composites are marked 
    'by the number of distinct prime factors. 
    'Check for a run of k ks 
    run = 0 
    For i = 2 To n 
     If nums(i) = k Then 
      run = run + 1 
      If run = k Then 'we have a winner! 
       SieveK = i - k + 1 
       Exit Function 
      End If 
     Else 
      'reset run counter 
      run = 0 
     End If 
    Next i 
    SieveK = -1 
End Function 

SieveK(10^6,4)在不到一秒的時間內評估爲134043。該函數不會產生這個或下三個數字的因式分解，但這些都很容易找到。 SieveK(10^8,5)的計算結果爲-1，所以不會少於1億的5個連續數字，每個數字都有5個不同的素數因子。

備註：在這個答案的早期版本中，我有一個邏輯缺陷（這並沒有阻止輸出是正確的）。即 - 我只篩選了n的平方根，但如果例如一個數字m看起來像2x3x5xp與p素數，那麼即使p可能超過n的平方根，m也可能有4個不同的素數因子。我修改了算法來照顧這種可能性。