2 Replies - 1790 Views - Last Post: 29 December 2011 - 04:44 PM

#1 brawnyman713   User is offline

  • D.I.C Head
  • member icon

Reputation: 0
  • View blog
  • Posts: 139
  • Joined: 21-October 07

Prime number finder

Posted 27 October 2007 - 10:14 AM

Description: Simply enter the number you want. (Edit: DreamInCode added a bunch of newlines to my comments, so you need to either delete the comments yourself or add the # characters where needed)Prints all of the prime numbers up to the given number(This way is literally thousands of times more efficient than the way most people write it).
print "Enter a number: "
max_number = gets.to_i
number = 7
low_max = Math.sqrt(max_number)
base_primes = {}
current_pos = 0
prime = true

if max_number >= 2 # I need a few starter values
 puts "2"
 base_primes[current_pos] = 2
 current_pos = current_pos + 1
end # if
if max_number >= 3
 puts "3"
 base_primes[current_pos] = 3
 current_pos = current_pos + 1
end # if
if max_number >= 5
 puts "5"
 base_primes[current_pos] = 5
 current_pos = current_pos + 1
end # if
while number <= low_max # while number <= sqrt of max_number
                        # this will add all prime numbers up
                        # to low_max to the base_primes array
  for x in 0..base_primes.length  - 1
    if number % base_primes[x] == 0
     prime = false
    end # if
  end # for
  if prime == true
   base_primes[current_pos] = number
   current_pos = current_pos + 1
   puts number
  end # if
  prime = true
  number = number + 2
end # while

prime = true
l_length = base_primes.length - 1
current_position = 0
while number <= max_number # Starting at the first number after low_max
                           # simply print all primes
  while prime == true and current_position <= l_length
    if number % base_primes[current_position] != 0
     prime = true
    else
     prime = false
    end # if
   current_position = current_position + 1
  end # while
  if prime == true
   puts number
  end # if
 current_position = 0
 prime = true
 number = number + 2
end # while


Is This A Good Question/Topic? 0
  • +

Replies To: Prime number finder

#2 brawnyman713   User is offline

  • D.I.C Head
  • member icon

Reputation: 0
  • View blog
  • Posts: 139
  • Joined: 21-October 07

Re: Prime number finder

Posted 27 October 2007 - 10:14 AM

Description: Simply enter the number you want. Quite frankly, a high level interpreted language like ruby is terrible for number crunching, because it's so much slower then compiled languages like C. It's more of a demonstration of an algorithm then anythingPrints all of the prime numbers up to the given number in a way that has no significant slowdown as the numbers get larger
print "Enter a number: "
max_number = gets.to_i
number = 7
low_max = Math.sqrt(max_number)
base_primes = {}
current_pos = 0
prime = true

if max_number >= 2 # I need a few starter values
 puts "2"
 base_primes[current_pos] = 2
 current_pos = current_pos + 1
end # if
if max_number >= 3
 puts "3"
 base_primes[current_pos] = 3
 current_pos = current_pos + 1
end # if
if max_number >= 5
 puts "5"
 base_primes[current_pos] = 5
 current_pos = current_pos + 1
end # if
while number <= low_max # while number <= sqrt of max_number
                        # this will add all prime numbers up
                        # to low_max to the base_primes array
  for x in 0..base_primes.length  - 1
    if number % base_primes[x] == 0
     prime = false
    end # if
  end # for
  if prime == true
   base_primes[current_pos] = number
   current_pos = current_pos + 1
   puts number
  end # if
  prime = true
  number = number + 2
end # while

prime = true
l_length = base_primes.length - 1
current_position = 0
while number <= max_number # Starting at the first number after low_max
                           # simply print all primes
  while prime == true and current_position <= l_length
    if number % base_primes[current_position] != 0
     prime = true
    else
     prime = false
    end # if
   current_position = current_position + 1
  end # while
  if prime == true
   puts number
  end # if
 current_position = 0
 prime = true
 number = number + 2
end # while

Was This Post Helpful? 0
  • +
  • -

#3 gbertoli3   User is offline

  • DIC at Heart + Code
  • member icon

Reputation: 41
  • View blog
  • Posts: 1,166
  • Joined: 23-June 08

Re: Prime number finder

Posted 22 November 2011 - 08:34 AM

Wow, very nice. I love how it does not slow down when getting to higher numbers. Your method for finding primes works amazing.
Was This Post Helpful? 0
  • +
  • -

#4 Karel-Lodewijk   User is offline

  • D.I.C Addict
  • member icon

Reputation: 454
  • View blog
  • Posts: 864
  • Joined: 17-March 11

Re: Prime number finder

Posted 29 December 2011 - 04:44 PM

The sieve of eratosthenes snippet, http://www.dreaminco...snippet6419.htm does the same. And in my benchmark generating primes to 10000000 without printing them, it is 20x faster.
Was This Post Helpful? 0
  • +
  • -

Page 1 of 1