dingleberry
Programmer
I was bored about a week ago and that got me to thinking. I did not know of a function to calculate prime numbers (and there might be one but I couldn't find it.) I decided to write one. Basically it starts with a range of numbers (10000) and starts at 1. It takes every number up to that number and runs a fmod function on it to determine if there is any remainder. You can imagine however that this function is wildly resourse intensive as the number increases because if for instance the number is 1111, the computer needs to calculate 1111/1 (match) and 1111/2 (no match) and 1111/3 (no match) etc until it get's more than 2 matches and then the loop exits and the number goes to 1112 and it starts all over again. To make this function lean as possible I've added a few immediate checks to kill the loop if true such as if the number is even we know it's not a prime and if the sum of the numbers of the number equals nine we know it's divisible by nine so that kills the loop (for instance 2322 -- 2+3+2+2=9 so 2322/9 is 258.) Also because we know the numerator is odd due to the fact that the function immediately throws out even numbers so that if the demoninator is even, we increase the denominator by 1 to make it odd because an odd divided by an even will always have a remainder.
I'm looking for some more tests to run to kill this loop if true or false. Any suggestions appreciated.
Another issue is my install of php does not include the str_split function and I don't know why so I had to write one at the bottom of the program and call that. Anyone know why str_split is not a valid function in my situation? Is that part of a library or something I did not compile with?
I've attached the program below. Use it if you want and modify it as you see fit but let me know what you do to make this more efficient. Currently I can only run about 5450 numbers before the 30 second timeout occurs. My goal would be to get it to 10000 or higher.
<?
$number = 10000;
$x = 1;
$count=0;
$y=1;
$g=2;
while ($x <= $number)
{
$even=fmod($x, $g);
if ($even==0)
{
# this means that we have an even numerator so count goes to three to disrupt following while loop.
$count=3;
}
else if (array_sum(str_split($x))==9)
{
$count=3;
# this means that the sum of the integers of the number is nine which means it's divisable by nine.
}
while (($count<=2) && ($y<=$x))
{
$yeven = fmod($y, $g);
if ($yeven==0)
{
# this means that the denominator is even in the equation and because we know that our numerator is odd due to the last loop, we can exclude it.
# echo "for $x we bombed here because y is $y<br>";
$y++;
}
$z=fmod($x, $y);
if ($z==0)
{
$y++;
$count++;
}
else if ($z<>0)
{
$y++;
}
}
if ($count <= 2)
{
echo "$x is a prime<br>";
}
$count=0;
$y=1;
$x++;
}
function str_split($split_length)
{
preg_match_all('/.{1,' . $split_length . '}/s', $string, $matches);
return $matches[0];
}
?>
Thanks,
Dan
I'm looking for some more tests to run to kill this loop if true or false. Any suggestions appreciated.
Another issue is my install of php does not include the str_split function and I don't know why so I had to write one at the bottom of the program and call that. Anyone know why str_split is not a valid function in my situation? Is that part of a library or something I did not compile with?
I've attached the program below. Use it if you want and modify it as you see fit but let me know what you do to make this more efficient. Currently I can only run about 5450 numbers before the 30 second timeout occurs. My goal would be to get it to 10000 or higher.
<?
$number = 10000;
$x = 1;
$count=0;
$y=1;
$g=2;
while ($x <= $number)
{
$even=fmod($x, $g);
if ($even==0)
{
# this means that we have an even numerator so count goes to three to disrupt following while loop.
$count=3;
}
else if (array_sum(str_split($x))==9)
{
$count=3;
# this means that the sum of the integers of the number is nine which means it's divisable by nine.
}
while (($count<=2) && ($y<=$x))
{
$yeven = fmod($y, $g);
if ($yeven==0)
{
# this means that the denominator is even in the equation and because we know that our numerator is odd due to the last loop, we can exclude it.
# echo "for $x we bombed here because y is $y<br>";
$y++;
}
$z=fmod($x, $y);
if ($z==0)
{
$y++;
$count++;
}
else if ($z<>0)
{
$y++;
}
}
if ($count <= 2)
{
echo "$x is a prime<br>";
}
$count=0;
$y=1;
$x++;
}
function str_split($split_length)
{
preg_match_all('/.{1,' . $split_length . '}/s', $string, $matches);
return $matches[0];
}
?>
Thanks,
Dan