loop for prime numbers

Asperon · September 15, 2007

Is there a limit to how many times a for loop will loop?

I have two functions that are set to do a prime number check this one is the first one.

In this code, the user puts in a number and the php divides it by all possible numbers, outputs those numbers and declares whether or not the number is prime. but if you put in a really big number ie. 74490223 it will do all the divisions but at the end, it won't declare prime or not, this isn't too big a deal because if it only echos 74490223 and 1 then the number is prime, but I don't know why it won't echo the "Prime" or "Not Prime" after a certain point.

<?php

$x = $_GET['prime'];
$count = 0;

?>
<html>
<head>
<title>TEST</title>
</head>
<body>

<form method="GET" action="test.php">
<input type="text" name="prime" />
<input type="submit" value="submit" />
</form>

<?php

for($i=1;$i<=$x;$i++){

$y = $x/$i;
$z = floor($x/$i);

if($y == $z){

echo $y.'<br />';
$count+=1;
}

}



if($count == 2){

echo 'Prime';

}
else{

echo 'Not Prime';

}

?>

</body>
</html>

The second one asks the user to input a number, the php will then find all of the prime numbers from 1 to that number. ie. if the user puts in 20 it will output 2 3 7 11 13 17 19..all of the prime numbers, but...if you put in a larger number like 15000 it will stop at about 11000 is it being limited by something? here is the code:

<?php

$x = $_GET['prime'];

?>
<html>
<head>
<title>TEST</title>
</head>
<body>

<form method="GET" action="prime.php">
<input type="text" name="prime" />
<input type="submit" value="submit" />
</form>

<?php


for($j=1;$j<=$x;$j++){

$count = 0;

if(floor($j/2)*2 == $j/2*2){
//this will prevent the number 2 from outputting but 2 is a known prime so its ok
}
else{

for($i=1;$i<=$j;$i++){

$y = $j/$i;
$z = floor($j/$i);

if($y == $z){

$count+=1;
$array[$i] = $y;


}

}

}


if($count == 2){

echo $array[1].' ';

}

}

?>

</body>
</html>

cooldude832 · September 15, 2007

php really isn't the engine to test prime numbers in, beyond that the proof of a prime number over 10 million is astronomical (around 1X10^6 factorial). If you really want to do a prime number summation find an algorithm to support the discovery of prime numbers and use that vs a check of a*b where a and b are integers thats product is equal to the given quantity. Your system seems to run this check a*b from a and b are less than the quantity given.

Asperon · September 15, 2007

well the the code takes the input number through a loop and divides it by every integer from 1 to its self. if the output has only 2 integers..1 and its self, then then number is prime, both sets of code do that, and it works when you test it, but the second one for some reason won't process more than 12000 numbers or so, I wanted to know if it was something with my code. I'm working on a proof that states that for all positive integers way out at infinity you will always be able to find two primes numbers that are seperated by 2 ie. 7 and 11 or even 104681 and 104683. but I wanted to be able to create my own list of primes etc

rarebit · September 15, 2007

You want to use certificates, i.e. known things you can check for quickly so that you don't have to check everything, e.g. div by 2, 5, 10, etc...

This page has some good titbits for fast math: http://lab.polygonal.de/2007/05/10/bitwise-gems-fast-integer-math/

There's lot's of big number libraries about, however python is one naturally, but it can be slow...

Instead of floor(x/y), try using modulo which is the % symbol, e.g. if((x % y) == 0), this should save you a function call...

As for your loop q, dunno?

For research look up Turing and DTM...

Barand · September 15, 2007

well the the code takes the input number through a loop and divides it by every integer from 1 to its self. if the output has only 2 integers..1 and its self, then then number is prime,

You can save some processing - you only need to loop as far as the sqrt of the number

This method uses the "Sieve of RustyKnees" to filter out prime numbers

<?php
if (isset($_GET['sub']))
{
    $ar = range (0, $_GET['num']);
    unset ($ar[0]);
    $lim =ceil(sqrt($_GET['num']));
    {
        for ($i=2; $i<$lim; $i++)
        {
            if (isset($ar[$i]))
            for ($j=2*$i; $j<=$_GET['num']; $j+=$i)
            {
                unset($ar[$j]);
            }
        }
    }
}
echo '<pre>', print_r($ar, true), '</pre>';
?>
<form>
Number <input type="text" name="num" size="12" /><br />
<input type="submit" name="sub" value="Get primes">
</form>

cooldude832 · September 16, 2007

Yeah, really you should start with a predefined list of prime numbers up to 100 thousand or something. Because that will remove your list of 100 thousand numbers down to a more realistic list of about 1000 to check.

kathas · September 16, 2007

You can save some processing - you only need to loop as far as the sqrt of the number

In fact this is still a waste of processing...

Check wikipedia Primality test

Check "Naive Methods" cause even if they are called naive they are the only ones that you can be 100% certain for their results...

Here is another article about the sieve of Atkin which even has a pseudocode version of it...

Also another thing because we are programming in php...

The pseudocode given, even Barand's code is ineffective when you put in big numbers (ex.: 100000).

PHP default configuration can't allocate the memory needed to create such a big list... So i guess the most effective method to check primality in PHP is to check (divide the supposed to be prime(n) with) numbers of the format 6k(+ or -)1 and up to sqrt(n).

But still cause we have a max time execution limit we would need to check which way would be more effective. That means even the most naive method or the most effective may not be able to calculate the primes in PHP up to a number as big as 100000

corbin · September 16, 2007

I got bored yesterday, and I'm trying to teach my self C++ so I wrote a small app in C++ that generates Prime numbers. It worked where you put in i and it would find i prime numbers. For example if you put in 5 it would find 2 3 5 7.

It generated 100,000 prime numbers (not prime numbers up to 100,000, but 100k prime numbers) in about 20 minutes.... I'm pretty sure in PHP it would've been impossible or at least verrrryyyy time consuming.

On a side note, the 100,000th prime number is 1.29971e+006 ;p.

Wait.... I don't think that's prime....

1.29971*10^6... 1299710... grrrr.... That's divisible by 10.... Wtf.... I guess since I used the float data type it shaved off some accuracy or something..... Bah!

*goes back to messing with it*

MmmVomit · September 20, 2007

If you're coding it in C++, you should go out and look for some type of BigInt class.

BTW, the 100,000th prime is going to be much, much, MUCH larger than a million. If that's the actual value your algorithm gave, you need to check your algorithm.

Barand · September 20, 2007

I just ran my code (above) with a max value of 1,299,710 and it produces an array of 100,001 prime numbers, the last 2 being

1299689

1299709

BTW, took about 6 seconds.

Results:

[pre]

Max : 1299710

Primes : 100001

Highest : 1299709

Time taken : 5.693 secs

Max : 2000000

Primes : 148934

Highest : 1999993

Time taken : 8.694 secs

Max : 3000000

Primes : 216817

Highest : 2999999

Time taken : 13.320 secs

Max : 4000000

Primes : 283147

Highest : 3999971

Time taken : 17.659 secs

Max : 5000000

Primes : 348514

Highest : 4999999

Time taken : 22.646 secs

Max : 6000000

Primes : 412850

Highest : 5999993

Time taken : 27.018 secs

Max : 7000000

Primes : 476649

Highest : 6999997

Time taken : 31.854 secs

Asperon · September 21, 2007

all very interesting, I never got far into c++ though I should get to know it better, also, most numbers after 2.0 x 10 ^300 output as 'infinity'...which I don't like, I'm working on a thereom that will prove that from 1 to inf you will always be able to find prime numbers that 2 apart... ie. 11,13---107,109----104681,104683...so I'm looking for that invisible pattern..I'm breaking it all down first, I have a list of the first 10,000 primes, but I wanted to generate more.... I started encoding them to try to make it easier to see patterns...

example:

**Note**I just took a chunk of each, so where they end is different...but you get the idea

Primes:

2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 101 103 107 109 113 127 131 137 139 149 151 157 163 167 173 179 181 191 193 197 199 211 223 227 229 233 239 241 251 257 263 269 271 277 281 283 293 307 311 313 317 331 337 347 349 353 359 367 373 379 383 389 397 401 409 419 421 431 433 439 443 449 457 461 463 467 479 487 491 499 503 509 521 523 541 547 557 563 569 571 577 587 593 599 601 607 613 617 619 631 641 643 647 653 659 661 673 677 683 691 701 709 719 727 733 739 743 751 757 761 769 773 787 797 809 811 821 823 827 829 839 853 857 859 863 877 881 883 887 907 911 919 929 937 941 947 953 967 971 977 983 991 997 1009 1013 1019 1021 1031 1033 1039 1049 1051 1061 1063 1069 1087 1091 1093 1097 1103 1109 1117 1123 1129 1151 1153 1163 1171 1181 1187 1193 1201 1213 1217 1223 1229 1231 1237 1249 1259 1277 1279 1283 1289 1291 1297 1301 1303 1307 1319 1321 1327 1361 1367 1373 1381 1399 1409 1423 1427 1429 1433 1439 1447 1451 1453 1459 1471 1481 1483 1487 1489 1493 1499 1511 1523 1531 1543 1549 1553 1559 1567 1571 1579 1583 1597 1601 1607 1609 1613 1619 1621 1627 1637 1657 1663 1667 1669 1693 1697 1699 1709 1721 1723 1733 1741 1747 1753 1759 1777 1783 1787 1789 1801 1811 1823 1831 1847 1861 1867 1871 1873 1877 1879 1889 1901 1907 1913 1931 1933 1949 1951 1973 1979 1987 1993 1997 1999 2003 2011 2017 2027 2029 2039 2053 2063 2069 2081 2083 2087 2089 2099 2111 2113 2129 2131 2137 2141 2143 2153 2161 2179 2203 2207 2213 2221 2237 2239 2243 2251 2267 2269 2273 2281 2287 2293 2297

Spaces between them:

1 2 2 4 2 4 2 4 6 2 6 4 2 4 6 6 2 6 4 2 6 4 6 8 4 2 4 2 4 14 4 6 2 10 2 6 6 4 6 6 2 10 2 4 2 12 12 4 2 4 6 2 10 6 6 6 2 6 4 2 10 14 4 2 4 14 6 10 2 4 6 8 6 6 4 6 8 4 8 10 2 10 2 6 4 6 8 4 2 4 12 8 4 8 4 6 12 2 18 6 10 6 6 2 6 10 6 6 2 6 6 4 2 12 10 2 4 6 6 2 12 4 6 8 10 8 10 8 6 6 4 8 6 4 8 4 14 10 12 2 10 2 4 2 10 14 4 2 4 14 4 2 4 20 4 8 10 8 4 6 6 14 4 6 6 8 6 12 4 6 2 10 2 6 10 2 10 2 6 18 4 2 4 6 6 8 6 6 22 2 10 8 10 6 6 8 12 4 6 6 2 6 12 10 18 2 4 6 2 6 4 2 4 12 2 6 34 6 6 8 18 10 14 4 2 4 6 8 4 2 6 12 10 2 4 2 4 6 12 12 8 12 6 4 6 8 4 8 4 14 4 6 2 4 6 2 6 10 20 6 4 2 24 4 2 10 12 2 10 8 6 6 6 18 6 4 2 12 10 12 8 16 14 6 4 2 4 2 10 12 6 6 18 2 16 2 22 6 8 6 4 2 4 8 6 10 2 10 14 10 6 12 2 4 2 10 12 2 16 2 6 4 2 10 8 18 24 4 6 8 16 2 4 8 16 2 4 8 6 6 4 12 2 22 6 2 6 4 6 14 6 4 2 6 4 6 12 6 6 14 4 6 12 8 6 4 26 18 10 8 4 6 2 6 22 12 2 16 8 4 12 14 10 2 4 8 6 6 4 2 4 6 8 4 2 6 10 2 10 8 4 14 10 12 2 6 4 2 16 14 4 6 8 6 4 18 8 10 6 6 8 10 12 14 4 6 6 2 28 2 10 8 4 14 4 8 12 6 12 4 6 20 10 2 16 26 4 2 12 6 4 12 6 8 4 8 22 2 4 2 12 28 2 6 6 6 4 6 2 12 4 12 2 10 2 16 2 16 6 20 16 8 4 2 4 2 22 8 12 6 10 2 4 6 2 6 10 2 12 10 2 10 14 6 4 6 8 6 6 16 12 2 4 14 6 4 8 10 8 6 6 22 6 2 10 14 4 6 18 2 10 14 4 2 10 14 4 8 18 4 6 2 4 6 2 12 4 20 22 12 2 4 6 6 2 6 22 2 6 16 6 12 2 6 12 16 2 4 6 14 4 2 18 24 10 6 2 10 2 10 2 10 6 2 10 2 10 6 8 30 10 2 10 8 6 10 18 6 12 12 2 18 6 4 6 6 18 2 10 14 6 4 2 4 24 2 12 6 16 8 6 6 18 16 2 4 6 2 6 6 10 6 12 12 18 2 6 4 18 8 24 4 2 4 6 2 12 4 14 30 10 6 12 14 6 10 12 2 4 6 8 6 10 2 4 14 6 6 4 6 2 10 2 16 12 8 18 4 6 12 2 6 6 6 28 6 14 4 8 10 8 12 18 4 2 4 24 12

Letters to correspond to the difference of the primes:

A A B A B A B C A C B A B C C A C B A C B C D B A B A B G B C A E A C C B C C A E A B A F F B A B C A E C C C A C B A E G B A B G C E A B C D C C B C D B D E A E A C B C D B A B F D B D B C F A I C E C C A C E C C A C C B A F E A B C C A F B C D E D E D C C B D C B D B G E F A E A B A E G B A B G B A B J B D E D B C C G B C C D C F B C A E A C E A E A C I B A B C C D C C K A E D E C C D F B C C A C F E I A B C A C B A B F A C Q C C D I E G B A B C D B A C F E A B A B C F F D F C B C D B D B G B C A B C A C E J C B A L B A E F A E D C C C I C B A F E F D H G C B A B A E F C C I A H A K C D C B A B D C E A E G E C F A B A E F A H A C B A E D I L B C D H A B D H A B D C C B F A K C A C B C G C B A C B C F C C G B C F D C B M I E D B C A C K F A H D B F G E A B D C C B A B C D B A C E A E D B G E F A C B A H G B C D C B I D E C C D E F G B C C A N A E D B G B D F C F B C J E A H M B A F C B F C D B D K A B A F N A C C C B C A F B F A E A H A H C J H D B A B A K D F C E A B C A C E A F E A E G C B C D C C H F A B G C B D E D C C K C A E G B C I A E G B A E G B D I B C A B C A F B J K F A B C C A C K A C H C F A C F H A B C G B A I L E C A E A E A E C A E A E C D O E A E D C E I C F F A I C B C C I A E G C B A B L A F C H D C C I H A B C A C C E C F F I A C B I D L B A B C A F B G O E C F G C E F A B C D C E A B G C C B C A E A H F D I B C F

There are certain rules you start to identify....like the A A (2 2) rule, the first two A's are the only time you will see them in pairs...after that, they are always isolated, C's (6) commonly come in 2's or 3's C C or C C C...C's are the most common in the pattern. etc. They also gradually spread out, 2,4,6,soon 20 etc, but keep the lower numbers present as well

MmmVomit · September 21, 2007

I just ran my code (above) with a max value of 1,299,710 and it produces an array of 100,001 prime numbers, the last 2 being

Yeah, you're right. That really suprises me, but looking at some lists of primes, the nth prime will be somewhere around 11 or 12 times n.

effigy · September 21, 2007

Pseudocode_for_programs_to_find_primes

corbin · September 26, 2007

Ahhh my C++ code was terribly inneffecient ;p. I've been trying to teach my self C++, and I'm at a lack of ideas for things to try to code, so I've been coding random things in it, and this sounded like a fun one to try ;p. I ended up using long double for the data type. I'm quite embarrassed at the time it takes to generate numbers, but then again, I'm new to C++, and not much of a math person (well, I'm decent at basic math ;p).

I generated up to the 1,000,000th prime just to see how long it would take (I don't remember now how long it took!), and the 1,000,000th prime is 15476731 (assuming everything went correctly ;p).

I can't find my C++ code, but it was something like this incase anyone is interested, although much, much better methods have been suggested. Bleh I'll do it in PHP really quickly:


function Prime($number) {

   $sr = ceil(sqrt($number));

   for($i = 2; $i < $sr; $i++) {
      if(Divisible($number, $i)) return false;
   }
   return true;
}

function Divisible($num1, $num2) {
   $r = $num1/$num2;
   if($r == round($r)) return true;
   return false;
}

Bleh... Once again, so no one feels the need to tell me, I know that's terribly ineffecient. Even the PHP code is a little... bleh. ;p

Daniel0 · September 26, 2007

For your Divisible() function, this would probably be better:

function Divisible($num1, $num2)
{
return $num1 % $num2 == 0;
}

corbin · September 26, 2007

Ahhh good call.... I didn't make the connection that that modulus of an even division would be 0 ;p.

Sign In

loop for prime numbers

Recommended Posts

Link to comment

Share on other sites

Link to comment

Share on other sites

Link to comment

Share on other sites

Link to comment

Share on other sites

Link to comment

Share on other sites

Link to comment

Share on other sites

Link to comment

Share on other sites

Link to comment

Share on other sites

Link to comment

Share on other sites

Link to comment

Share on other sites

Link to comment

Share on other sites

Link to comment

Share on other sites

Link to comment

Share on other sites

Link to comment

Share on other sites

Link to comment

Share on other sites

Link to comment

Share on other sites

Join the conversation

Important Information