help writing prime finding program

need a help with a new sieve technique

Page 1 of 1

11 Replies - 2932 Views - Last Post: 12 June 2007 - 01:52 AM Rate Topic: -----

#1 nightgamer360  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 20
  • Joined: 08-February 07

help writing prime finding program

Posted 05 June 2007 - 09:07 PM

is thier any way to modify this java program to work in c++ with large numbers?

I hope i have this pasted right

http://www.math.com/...rime-number.htm


I have access to a couple of c++ compilers I am learning on.

<!-- Begin

function calculate(form) {

var num=parseInt(form.number.value);

if (isNaN(num) || num < 0) {

form.result.value=(form.number.value + " is not a valid number!  Try again!");

}

if (num == 1) {

form.result.value=("1 is not prime by definition!");

}
if (num == 0) {

form.result.value=("0 is not a valid number.");

}
if (num == 2) {

form.result.value=("2 is a prime number!");
}



for (var i=2;i<num;i++) {

if (num % i == 0) {

var prime="yes";

form.result.value=(num + " is not prime.  It is divisible by " + i + ".");

break;

}

if (num % i != 0) var prime="no";

}

if (prime == "no") form.result.value=(num + " is prime!");

} 

// End -->

</SCRIPT>
	  <P align="left"> 
	  <div align="left"> 
		<table width="100%" border="0" cellspacing="2" cellpadding="2">

		  <tr> 
			<td> 
			  <div align="left"><font size=6><font size="+2" align=RIGHT color="#0000FF"><font color="#CC6600" size="+1">Prime 
				Number</font></font><br>
				</font> 
				<table border=0 width=486 cellpadding=3 cellspacing=0>
				  <tr> 
					<td>Enter a number and the Prime Number Calculator will instantly 
					  tell you if it is a prime number or not.</td>
				  </tr>
				</table>
			  </div>

			  <form name=form>
				<div align="left"> 
				  <p>Please enter a number: 
					<input type=text name=number size=10>
					<br>
					<input type=button value="Is it prime?" onclick="calculate(this.form)" name="button">
					<input type=text name=result size=45 value="">
					<br>
				  </p>
				</div>

			  </form>
			</td>
		  </tr>
		  <tr> 
			<td>Prime numbers are positive, non-zero numbers that have exactly 
			  two factors -- no more, no less.</td>
		  </tr>
		</table>
	  </div>
	  <hr>

	  <div align="right"><br>
</div>
	  <P align="left">  
	  <!-- #EndEditable --></td>
	<td>  </td>
	<td valign="top">
		<table width="0" border="0" cellspacing="0" cellpadding="0">


any help much appreciated. If your writing a sieve program for programmers it will be of value for you to do 2 things

#1. Look at a list of primes such as found at the first 1,000 primes at

http://primes.utm.ed.../small/1000.txt

and please note that each prime ends in 1,3,7 or 9 only. This means you can greatly increase your odds of finding primes by chosing numbers that end in 1,3,7 or 9 and you may look at even larger primes and you will see that all end in either 1,3,7 or 9.

#2 that no composite you find will have a whole number divisor more
than 50% its value (other than the number itself), for example the highest whole number divisor of 16 is 8, 8 is 50% of 16. You can enter each composite you find and it will say its highest whole number divisor is not more than 50% of the value of the number entered.

This means you only have to use 1/2 the numbers of the number being tested for primality instead of diving the number of times of the number tested using a sieve program. I invite you to use a percent calculator or do the math yourself calculate what percent of the highest whole number divisor of any composite is you find, no composites highest whole number divisor will be more than 50% of its value (other than the composite itself).

For example to find out if 16 has two divisors of one and
itself you normally would divide 16 by numbers 1-16. Instead all
you will have to do is find 50% of the number you wish and do numbers
1-50% of the number entered in this case divide 16 by numbers 1-8 to find if 16 has a whole number divisor. That should save you half the time.

thought that might help prime finders save some time :).

By the way an easy way of finding out 50% of a number or amount, divide the number by 2. you can round down to the nearest whole number if it ends in a decimal (.50).

This post has been edited by jayman9: 10 June 2007 - 10:45 AM


Is This A Good Question/Topic? 0
  • +

Replies To: help writing prime finding program

#2 PennyBoki  Icon User is offline

  • system("revolution");
  • member icon

Reputation: 53
  • View blog
  • Posts: 2,334
  • Joined: 11-December 06

Re: help writing prime finding program

Posted 06 June 2007 - 05:36 PM

Hi, first the code you have is not a java program.
What seems to be the problem are you having trouble with modifying that code in c++ or ...
Was This Post Helpful? 0
  • +
  • -

#3 salindor  Icon User is offline

  • D.I.C Regular
  • member icon

Reputation: 46
  • View blog
  • Posts: 301
  • Joined: 10-November 06

Re: help writing prime finding program

Posted 06 June 2007 - 06:45 PM

It seems like you are partially looking for an algorithm....

Here is one that several big number random prime generators use for finding primes with > 512 bits.

http://en.wikipedia...._primality_test

If I remember right, there are some very rare but large numbers which can pass the test and not be prime (and they can pass all the tests you mentioned above).

However, in practice, I think the probability of finding those is small enough to not matter.

Salindor
Was This Post Helpful? 0
  • +
  • -

#4 nightgamer360  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 20
  • Joined: 08-February 07

Re: help writing prime finding program

Posted 08 June 2007 - 01:38 AM

View Postsalindor, on 6 Jun, 2007 - 06:45 PM, said:

It seems like you are partially looking for an algorithm....

Here is one that several big number random prime generators use for finding primes with > 512 bits.

http://en.wikipedia...._primality_test

If I remember right, there are some very rare but large numbers which can pass the test and not be prime (and they can pass all the tests you mentioned above).

However, in practice, I think the probability of finding those is small enough to not matter.

Salindor.

Actually the tests are for finding primes but perhaps youve confused the issue a prime has no whole number divisors other than one and the number tested a
composite doesnt have a whole number divisor more than 50% its value (no decimal number) other than the number being tested itself.

because a prime has no whole number divisors (other than one or itself) and a composite doesnt have a whole number divisor more than half its value wich is why you dont have to use all the numbers to find out if the number is prime.

A composite never has a number more than half its value as a whole number divisor. In fact i have extensively checked and invite you to do the same and find a prime that does not end in 1,3,7 or 9 and ask around as Im geniunely interested in finding if thats true other than 2 and 5.

Id also like you to find for me a composite or ask around if thier are large composites with composites or primes as whole number divisors that have a whole number divisor ( no decimal) that is more than half the value of the composite tested (other than the number tested itself of course wich is 100% of its value and has itself as a divisor, all whole numbers do).
happy hunting!
Ive extensively checked for any prime that doesnt fit the criteria of 1,3,7 and 9 at

http://primes.utm.edu/

and invite you to do the same.


I invite you to be specific and point the way with that information as well with a number, website, person with that specific number or composite that has
a whole number divisor (no decimal) more than 50% its value.


I assumed this was in java because it was in html but I may be in error as I'm pretty new to programming. Actually I am more interested in what the program is doing especially showing the lowest possible whole number divisor other than one and was wondering if i could modify it to work with large numbers.

This post has been edited by nightgamer360: 08 June 2007 - 03:11 AM

Was This Post Helpful? 0
  • +
  • -

#5 nightgamer360  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 20
  • Joined: 08-February 07

Re: help writing prime finding program

Posted 08 June 2007 - 02:07 AM

View PostPennyBoki, on 6 Jun, 2007 - 05:36 PM, said:

Hi, first the code you have is not a java program.
What seems to be the problem are you having trouble with modifying that code in c++ or ...


actually im new to programming and wondering I assumed it was in java as its in html. Id like to be able to modify the program to work in c++ with large numbers as im interested in what its doing with showing the lowest possible whole number divisor other than one of the number being inputed that is not a prime.
Was This Post Helpful? 0
  • +
  • -

#6 Trogdor  Icon User is offline

  • D.I.C Addict
  • member icon

Reputation: 15
  • View blog
  • Posts: 627
  • Joined: 06-October 06

Re: help writing prime finding program

Posted 08 June 2007 - 05:36 AM

that sniplet that you forgot to put between [ code ] tags is javascript. It also is a very bad implementation of a primefinding algorithm.

I suggest you follow this path:

First you try to understand how the sieve algorithm works. or any other algorithm you want to use for that matter. Try it out on paper. Use wikipedia. Ask your math teacher.

Then, when you understand the algorithm, try to mold it into code.
Was This Post Helpful? 0
  • +
  • -

#7 nightgamer360  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 20
  • Joined: 08-February 07

Re: help writing prime finding program

Posted 09 June 2007 - 01:46 AM

thanks i understand what the algorithm is doing, my question is can it be implimented to use large numbers and im assuming you'd need a c+ or c compiler to be able to do that as most webpage based number program have number limits (and small number limits). i have my own personal reasons for doing this and am probably just going to pay someone to do it based on some of the responses ive been getting. thanks for the help.

my math skills are pretty nifty and a math teacher isnt needed, its finding a good programmer that doesnt say hey just figure it out. lol.
Was This Post Helpful? 0
  • +
  • -

#8 salindor  Icon User is offline

  • D.I.C Regular
  • member icon

Reputation: 46
  • View blog
  • Posts: 301
  • Joined: 10-November 06

Re: help writing prime finding program

Posted 09 June 2007 - 08:03 AM

I apologize I misunderstood what you were asking for. As far as your previous post goes responding to my post you only have to test up to the sqrt(x). So you can improve the effiency of your algorithm by stopping there instead. The heuristics you gave are all good tests, I a have used all of them myself.

To give you an idea of how slow your algorithm will become:
A might number falls

Normally what I do is perform all the hueristics your described above, test all primes smaller than 1024, and then doing a rabin millir primilality test for a .001 proability.

Salindor
Was This Post Helpful? 0
  • +
  • -

#9 NickDMax  Icon User is offline

  • Can grep dead trees!
  • member icon

Reputation: 2250
  • View blog
  • Posts: 9,245
  • Joined: 18-February 07

Re: help writing prime finding program

Posted 09 June 2007 - 09:42 PM

You can make a program for dealing with larger numbers in Javascript. The process is not even all that different from doing things in a language such as C/C++ as the key is to use an array. Java script has the slight disadvantage of being loosely typed which may complicate the logic a little, but once you have that sorted out the steps are about the same in Javascript as they would be in c/c++. The big problem with finding prime numbers larger than what can fit in an integer in Javascript is the time required. Javascript will be very slow.
Was This Post Helpful? 0
  • +
  • -

#10 nightgamer360  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 20
  • Joined: 08-February 07

Re: help writing prime finding program

Posted 10 June 2007 - 02:08 AM

View PostNickDMax, on 9 Jun, 2007 - 09:42 PM, said:

You can make a program for dealing with larger numbers in Javascript. The process is not even all that different from doing things in a language such as C/C++ as the key is to use an array. Java script has the slight disadvantage of being loosely typed which may complicate the logic a little, but once you have that sorted out the steps are about the same in Javascript as they would be in c/c++. The big problem with finding prime numbers larger than what can fit in an integer in Javascript is the time required. Javascript will be very slow.


thanks for that. would it be neccessarily faster to build a program ground up using that in c++ or java? the only program i have found is factor calculator by dreamweaver i believe and they say to buy the program for 4.95 and when you do thier is no online registration code or instructions. the program crashes also at large numbers so im assuming that its a bogus program especially since thier main website has nothing to do with the program itself. I have access to several spendy compilers but little to no programing experience. I also have bloodshed.

do you know of any large number calculators as well that handle division and multiplication as most i have seen especially on webpages have small number limits? I understand what this algorithm is doing wich is why i want to use it, Im trying to just get it to factor large numbers and find the smallest possible whole number divisor of a number other than one or the number itself being tested.

is it also possible to create a prime testing program that will
divide through a specific number range? such as divide 100 by
numbers 1-70?

This post has been edited by nightgamer360: 10 June 2007 - 02:11 AM

Was This Post Helpful? 0
  • +
  • -

#11 NickDMax  Icon User is offline

  • Can grep dead trees!
  • member icon

Reputation: 2250
  • View blog
  • Posts: 9,245
  • Joined: 18-February 07

Re: help writing prime finding program

Posted 10 June 2007 - 10:12 AM

For C/C++ there are a number of libraries that you can use. A google search will get you a handful or so.

Big Integer Library

MAPM

BigDigits

Big Integers in Javascript

BigIntegers and RSA in Javascript This one is mostly crypto stuff, but the code from the BigInt is well done.

If you are interested in writing your own version on either language the classic algorithms are discussed in Knuth's "Art of Computer Programming, Volume 2: Seminumerical Algorithms" which you can find in just about any college library. There is also a pretty good book by Tom St Denis named "BigNum Math: Implementing Cryptographic Multiple Precision Arithmetic" which is nice because the libraries that are talked about are freely downloadable. This is very nice for understanding how the algorithms work.

Quote

is it also possible to create a prime testing program that will
divide through a specific number range? such as divide 100 by
numbers 1-70?


Why yes... if you mean loop though from 1 to 70 doing a division. Actually the more important operation is modulus. To find primes are you really want to know is if X is divisible by P. You could do a division an see if there were remainder, or you can use number theory to shorten the process to modular tests

Note, if you are asking to find prime somewhere within the first million or so you really don't have to use Arbitrary Precision Arithmetic. (perhaps in javascript). C/C++ has the unsigned long and unsigned long long data types which can easily reach up there. The max range of an unsigned long is usually about 4294967295 and the unsigned long long gets up to 18,446,744,073,709,551,615. -- With these you can use standard operations.
Was This Post Helpful? 0
  • +
  • -

#12 nightgamer360  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 20
  • Joined: 08-February 07

Re: help writing prime finding program

Posted 12 June 2007 - 01:52 AM

View PostNickDMax, on 10 Jun, 2007 - 10:12 AM, said:

For C/C++ there are a number of libraries that you can use. A google search will get you a handful or so.

Big Integer Library

MAPM

BigDigits

Big Integers in Javascript

BigIntegers and RSA in Javascript This one is mostly crypto stuff, but the code from the BigInt is well done.

If you are interested in writing your own version on either language the classic algorithms are discussed in Knuth's "Art of Computer Programming, Volume 2: Seminumerical Algorithms" which you can find in just about any college library. There is also a pretty good book by Tom St Denis named "BigNum Math: Implementing Cryptographic Multiple Precision Arithmetic" which is nice because the libraries that are talked about are freely downloadable. This is very nice for understanding how the algorithms work.

Quote

is it also possible to create a prime testing program that will
divide through a specific number range? such as divide 100 by
numbers 1-70?


Why yes... if you mean loop though from 1 to 70 doing a division. Actually the more important operation is modulus. To find primes are you really want to know is if X is divisible by P. You could do a division an see if there were remainder, or you can use number theory to shorten the process to modular tests

Note, if you are asking to find prime somewhere within the first million or so you really don't have to use Arbitrary Precision Arithmetic. (perhaps in javascript). C/C++ has the unsigned long and unsigned long long data types which can easily reach up there. The max range of an unsigned long is usually about 4294967295 and the unsigned long long gets up to 18,446,744,073,709,551,615. -- With these you can use standard operations.


thanks very much for the help, really appreciate that. yes i am also searching how to do looped functions for basic math such as adding one number repeatedly or dividing say 100 through numbers 1-70. My reason for this is to shorten times for proving a prime. an example would be to take 20 and add 30 to it and then repeatedly add 30 to each answer.

for the max range are you talking about digit amounts or is that the number itself?

is it also possible to get it to stop at a certain ending number if found as an answer when dividing? all composites have more than one divisor that ends in .50 while primes have only one, therefor all of the numbers would not have to be divided through for that as well in theory, just find two .50's to show its a composite.

as a matter of fact if any of you are writing prime finding programs it may be of help to tell your program to stop when it finds a whole number other than one instead of dividing all the numbers of the number tested to find primes because
if it has one whole number divisor other than one the number tested automatically is not a prime.

Do you know anything how gimps works? do they divide the number amount to be divided between computers or do they simply send out different numbers to different computers hoping to increase thier odds?

out of curiosity can any of you hit a prime or a composite number each time
with the algorithm to show?

id rather do the code myself but as im not sure what is capable in programming its often better to ask especially since i find no programs other than sieve of Eratosthenes programs.

This post has been edited by nightgamer360: 12 June 2007 - 02:08 AM

Was This Post Helpful? 0
  • +
  • -

Page 1 of 1