Относительно простых чисел VB

Question

У меня есть это число x, и я хотел найти все числа, которые относительно просты для него.

мой код до сих пор:

 For i = 1 To x-1
        if [number n is relatively prime to x] Then
             ListBox1.Items.Add(x)
        End If
  Next

Заранее спасибо

Answer 1

Два числа являются относительно простыми, если их наибольший общий делитель равен 1. VB не имеет встроенной функции GCD, но алгоритм достаточно прост (и около 2300 лет!):

function gcd(m, n)
    while n > 0
        m, n = n, m%n
    return m

Обратите внимание, что m и n назначаются одновременно.Я оставлю это вам, чтобы завершить реализацию VB.Возможно, вас заинтересует поиск по номеру числа и список его значений, что вы и рассчитываете.

Answer 2

Предполагая, что вам нужны только числа, меньшие x, которые взаимно просты с ним - вы также можете использовать генеративный подход, используя специальный тип сита.Когда сгенерированы кратные каждого простого числа, вы увидите, если эта последовательность"достигнет" вашего верхнего предела x или пропустит его, и пометит все числа в нем как не взаимно простые, если он достигнетx.

Или в «псевдокоде» (с синтаксисом Haskell :)),

coprimes n = go( [1..n-1], [2..n-1]) where
  go( xs, []   ) = xs           -- ' no more numbers to sieve - return xs
  go( xs, p:ks ) =              -- ' p is first in candidates, ks is the rest
    let ms = [p, 2*p .. n-1]    -- ' p's multiples
    in
      go( if ( (mod n p) == 0 ) -- ' is n a multiple of p ?
            then (xs\\ms)       -- ' yes: remove p's multiples
            else xs,            -- ' no:  possible coprimes
          ks\\ms )              -- ' candidates to sieve

Разность множеств в Haskell \\ очень неэффективна с неупорядоченным представлением списков множеств, но вы, естественно, закодируете этоэффективно, поверх изменяемых массивов, в VB.