Jump to content



Photo

[Perl] Prime numbers


  • Please log in to reply
5 replies to this topic

#1 mtber

mtber

    Neowinian

  • Joined: 13-July 07
  • Location: United States (Vermont)

Posted 28 January 2008 - 15:29

I am trying to create a perl program that will find all of the prime numbers between 1 and 10. does anyone know of an equation that can be used with perl in order to get that. or am i looking at this all wrong.

Thanks


#2 JamesCherrill

JamesCherrill

    Neowinian

  • Joined: 14-November 03
  • Location: France

Posted 28 January 2008 - 16:49

There's no formula to generate all the primes. Either look at each number in turn and check if it's divisible by any of the (prime) numbers smaller than (the square root of) it, or start with an array of all the numbers then strike out all the multiples of 2, then all the multiples of 3, then 5 etc

#3 rpgfan

rpgfan

    Neowinian

  • Joined: 27-June 07

Posted 28 January 2008 - 20:07

I usually do something like what JamesCherrill described. I have a number that I take the square root of. If any integer is less than or equal to that square root, I test for divisibility by 3 (anything divisible by 2 is ignored because 2 is the only even prime, and anything less than 2 is not prime, so I just start a loop at 3 and increment by 2), by 5, by 7, not by 9 because that is already divisible by 3, by 11, 13, not by 15 because 15=3*5, 17, 19, and so on. In other words, I have an array that I append new primes to when they're found. A much longer, but less intensive test is to test against half of a given number rather than the square root of that number. If you need to generate primes between 1 and 10, then you could benefit from n/2 rather than sqrt(n) because a square root can cause issues in some cases if it isn't converted to an integer properly. If you needed something like 1 through 1000000, then I would go the square root route.

Edit:
I should note that several patterns have been found, but not very many can be applied using algorithms, because the patterns are more visual, like a sort of spiral created by arranging the numbers in a certain formation. One thing you might also consider is the idea that sometimes Mersenne primes are useful. They are prime numbers of the form Math.pow(2, exponent) - 1. In many cases, 2 less or 2 more than that a number using that equation can be prime. For a range like 1 through 10, that might work for you. However, the traditional and more useful one is the square root approach. There are other ways, but that is by far the simplest, in my opinion.

Edited by rpgfan, 28 January 2008 - 20:14.


#4 Shubhangam Agrawal

Shubhangam Agrawal

    Neowinian

  • Joined: 21-January 06

Posted 29 January 2008 - 12:58

is there a % operator in perl? the one that returns remainder?

if there is make something like:

input number = num

make a var x = 0

run a loop from 2 to the num/2 where if (num%[loop var] == 0), then x++

after the loop, if x = 0 , the number is prime, else its not ^_^

#5 kjordan2001

kjordan2001

    Mystery Solver

  • Tech Issues Solved: 1
  • Joined: 27-May 02

Posted 29 January 2008 - 13:43

There's no formula to generate all the primes. Either look at each number in turn and check if it's divisible by any of the (prime) numbers smaller than (the square root of) it, or start with an array of all the numbers then strike out all the multiples of 2, then all the multiples of 3, then 5 etc

Correct. More info on that technique: http://mathforum.org....prime.num.html

#6 OP mtber

mtber

    Neowinian

  • Joined: 13-July 07
  • Location: United States (Vermont)

Posted 29 January 2008 - 19:09

Ok Here is what i got so far. i have it printing the prime numbers from 0-10 but can anyone help me get it so that it will take a users input and find the prime numbers of that number the user input and if the user inputs a negative number then it will give an error

Thanks
#!
use strict;
my @list = 1..100;
foreach $a (@list){
	my@total=();
	foreach $b(@list){
	if ((int($a/$b)==($a/$b))){
	push @total, $b;
	}
	}
	print "$a is prime\n" if($#total == 1);
}