Archived

This topic is now archived and is closed to further replies.

[Perl] Prime numbers

Recommended Posts

mtber    0

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

Share this post


Link to post
Share on other sites
JamesCherrill    27

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

Share this post


Link to post
Share on other sites
rpgfan    0

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.

Share this post


Link to post
Share on other sites
Shubhangam Agrawal    0

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 ^_^

Share this post


Link to post
Share on other sites
kjordan2001    164
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/dr.math/faq/faq.prime.num.html

Share this post


Link to post
Share on other sites
mtber    0

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);
}

Share this post


Link to post
Share on other sites

  • Recently Browsing   0 members

    No registered users viewing this page.