Sign in to follow this  
Followers 0
mtber

[Perl] Prime numbers

6 posts in this topic

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

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

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

Share this post


Link to post
Share on other sites

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

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

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!


Register a new account

Sign in

Already have an account? Sign in here.


Sign In Now
Sign in to follow this  
Followers 0

  • Recently Browsing   0 members

    No registered users viewing this page.