SitePoint Sponsor

User Tag List

Results 1 to 2 of 2

Hybrid View

  1. #1
    SitePoint Member
    Join Date
    Nov 2008
    Posts
    1
    Mentioned
    0 Post(s)
    Tagged
    0 Thread(s)

    Script to find greatest prime factor.

    Will this work and/or what should I do to improve it?

    n = 2
    peter = gets
    until n > peter**0.5
    if peter % n == 0
    peter = peter / n
    n = 2
    else
    n = n + 1
    end
    end
    print peter

  2. #2
    SitePoint Addict ruby-lang's Avatar
    Join Date
    Aug 2007
    Posts
    389
    Mentioned
    0 Post(s)
    Tagged
    0 Thread(s)
    Code Ruby:
    input = gets.to_i
     
    # this code is the sieve of Eratosthenes, I just googled for it
    sieve = []
    for i in 2 .. input
      sieve[i] = i
    end
     
    for i in 2 .. Math.sqrt(input)
      next unless sieve[i]
      (i*i).step(input, i) do |j|
        sieve[j] = nil
      end
    end
     
    # here we look for the highest prime factor
    sieve.compact.reverse.each do |p|
      if input % p == 0
        print p
        exit
      end
    end


Bookmarks

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •