prime_numbers.rb

# count number of divisors of n

# O(n)
def slow_divisors(n)
  divisors = 0
  (1..n).each do |num|
    if n % num == 0
      divisors += 1
      puts "num: #{num}"
    end
  end
  divisors
end

# O(sqrt(n))
def divisors(n)
  divisors = 0
  i = 1
  while i * i < n
    divisors += 2 if n % i == 0
    i += 1
  end
  divisors +=1 if i * i == n
  divisors
end


#puts "total divisors: #{slow_divisors(100)}"

# O(n)
def slow_prime?(n)
  (2..n - 1).each do |num|
    return false if n % num == 0
  end
  true
end

# O(sqrt(n))
def faster_prime?(n)
  i = 2
  while i * i < n
    return false if n % i == 0
    i += 1
  end
  true
end

#puts faster_prime?(23)

# Each coin shows heads at start
# Q: How many coins, after flipping, show tails?
# O(n * n)
def coins(a)
  n = a.size
  (1..n).each do |i|
    c = 1
    # person i flips all coins with multiples of i
    while c * i <= n
      a[c * i - 1] = if a[c * i - 1] == 'H'
                       'T'
                     else
                       'H'
                     end
      c += 1
    end
  end
  tails = 0

  a.each do |coin|
    tails += 1 if coin == 'T'
  end
  tails
end

a = ['H'] * 10
# puts coins(a)

# O(n log n)
def faster_coins(n)
  # n = num of coins
  # p = person #
  # coin = array of coins (0 = H, 1 = T)
  # k = array index of coin we're flipping
  # tails = total # of tails after all coins flipped
  tails = 0
  coin = [0] * (n + 1)
  (1..n + 1).each do |p|
    k = p
    while k <= n
      puts "p: #{p}, k: #{k}, coin: #{coin}"
      coin[k] = (coin[k] + 1) % 2
      k += p
    end
    tails += coin[p]
    puts "tails: #{tails}"

  end
  puts "coin: #{coin}"
  tails
end

puts faster_coins(10)