prime number ,how ?

[phanbachloc]

:( i dont know how to test if one number is a primenumbrer,please help me.
:p i'll be thankful to you very much ,and i'll help u again

[Dillinger4]

Well you first have to define what a prime number is. It is a number that can only be divided evenly (not producing a remainder) by itself and one. {2,3,5,7,11,13,17,19,23} *~Note that zero and one are not prime numbers.

[Dillinger4]

I coded this but how to test for a prime number in code i am not too sure. Since you would have see if the number is evenly divisible by itself and one but not any other number.

import java.io.*;

class Example{
public static void main(String[] args){

int i = 0;
String input;

BufferedReader buff = new BufferedReader(new InputStreamReader(System.in));
System.out.println("Please enter a number to see if prime");

try{
input = buff.readLine();
i = Integer.parseInt(input);

isPrime(i);
}catch(IOException e){System.err.print(e);}
}
public static void isPrime(int i){
switch(i){
case 0:
System.out.println("0 cannot be divided by itself");
return;
case 1:
System.out.println("1 is not a prime number");
return;
}
int result = i / i;
if(result == 1){
System.out.println("The number" + i + "is a prime number");
return;
}
System.out.println("The number" + i + "is not a prime number");
}
}

[DavidHooper]

Have a look here (http://209.120.143.185/showthread.php?threadid=104395&highlight=prime+number) and here (http://209.120.143.185/showthread.php?threadid=163560&highlight=prime+number).

[[Digital-X-Treme]]

Originally posted by Dilenger4
I coded this but how to test for a prime number in code i am not too sure. Since you would have see if the number is evenly divisible by itself and one but not any other number.


int result = i / i;
if(result == 1){
System.out.println("The number" + i + "is a prime number");
return;
}
System.out.println("The number" + i + "is not a prime number");



That will not check if a number is prime. i/i will always evaluate to 1 for real numbers (excluding zero, which is undefined), so basically, any number you pass into the function would be flagged as being prime, when it might not be! :)

[Dillinger4]

That's what i was thinking after i coded that last night. :p All numbers when divided by themselves will produce one wether they are prime or not. I just figured i would take a stab at it. :D

[wy125]

*
* Primes.java
*
* Created on May 24, 2002, 9:07 AM
*/


public class Primes {



/**
* Is n a prime number?
*
* @return boolean true if n is prime, false if it's not
* @param n the number to test
*/
public static boolean isPrime (int n)
{


if (n <= 1) return false;



for (int i = 2; i <= java.lang.Math.sqrt(n); i++)
{
if (n % i == 0)
return false;
}

return true;
}


/**
* Print the first num Primes
*
* @param num the number of primes to print out starting from 1
*/
public static void printPrimes (int num)
{
if (num <= 0)
return;

int i, count;
for (i = 1, count = 0; count < num; i++)
{
if (Primes.isPrime(i))
{
System.out.println((count + 1) + ") " + i);
count++;
}
}
}






public static void main (String args[])
{

int i = 0;
System.out.println("Test\n");
System.out.println("\nPrint out the first 100 prime numbers\n");

Primes.printPrimes(1000);
}



}

[wy125]

*
* Primes.java
*
* Created on May 24, 2002, 9:07 AM
*/


public class Primes {



/**
* Is n a prime number?
*
* @return boolean true if n is prime, false if it's not
* @param n the number to test
*/
public static boolean isPrime (int n)
{


if (n <= 1) return false;



for (int i = 2; i <= java.lang.Math.sqrt(n); i++)
{
if (n % i == 0)
return false;
}

return true;
}


/**
* Print the first num Primes
*
* @param num the number of primes to print out starting from 1
*/
public static void printPrimes (int num)
{
if (num <= 0)
return;

int i, count;
for (i = 1, count = 0; count < num; i++)
{
if (Primes.isPrime(i))
{
System.out.println((count + 1) + ") " + i);
count++;
}
}
}






public static void main (String args[])
{

int i = 0;
System.out.println("Test\n");
System.out.println("\nPrint out the first 100 prime numbers\n");

Primes.printPrimes(1000);
}



}

[JPicasso]

You test by dividing every number by every odd integer over one up to the squareroot to see if anything evenly divides into it.

if it does, it ain't prime.

[jhermiz]

Basically a prime number is as has been mentioned a number only divisible by itself and 1. By definition 0,1 are not prime since 0/0 is indeterminate. A prime need not be tested against anything above 1/2 that prime. Meaning if I wanted to test if 25 was prime I need not test the value 13 since 13 > 25/2. In fact if we look a little closer we need not test anything > sqrt(n). Meaning we should only take values upto and including the sqrt of that number 'n' to determine whether 'n' is prime or not. So have a look at the following in C++...this can easily be translated into Java since all it is is for loops. The big O of the outer for loop is MAX which may be redifined and the inner j loop is big O of sqrt(n) where n is the value we are trying to test. At most we will loop n*sqrt(n) in case we dont break.

#include<math.h>
#include<iostream.h>

int main(void)
{
int isPrime;
const int MAX=50;

for(int i=2; i<=MAX; i++)
{
isPrime=1;
for(int j=2; j<=sqrt((i)); j++)
{
if(!(i%j))
{
isPrime=0;
break;
}
else
continue;
}
if(isPrime)
cout << i << " ";
}
return 0;
}

Cheers,

Jon

[MrPolite]

Originally posted by JPicasso
You test by dividing every number by every odd integer over one up to the squareroot to see if anything evenly divides into it.

if it does, it ain't prime. all those old stuff :p....
I never quite understood why we devide it bu the numbers that are smaller than the squareroot though...:rolleyes:

[smwwilson]

because every number has a prime factorization, that is, a bunch of prime numbers that when multiplied together, give you your number. if Z has a prime factor (X) bigger than its square root, then there must be a number (Y) when you multiply it by X gives you Z. if Y is greater than the square root of Z, than surely X times Y is greater than Z which is impossible. so Y must be less than the square root of Z, which means we will have found it by the time we get to square root of Z, which means that Z is not prime.

simply, there can be no 2 numbers bigger than the square root of z that when multiplied equal Z.

[sql_lall]

Some interesting evolutions of a prime program:
(Testing whether i = 1 to n is prime)
1) divide i by every number < i
2) divide i by every number < sqrt(i)
3) divide i by every odd number < sqrt(i)
4) divide i by every number (6K +/- 1) < sqrt(i)
5) divide i by every number (30K +1,7,11,13,17,19,23,29) <sqrt(i)
6) divide i by every number (210K +1,11.....) < sqrt(i)
7) divide i by every prime number <sqrt(i)
etc...
COMBINED WITH:
a) make i any number < n
b) make i any odd number < n
c) make i any number (6K +/- 1) < n
d) make i any number (30K +1,7,11,13,17,19,23,29) <n
e) make i any number (210K +1,11.....) < n
etc...


The big question is:
Does the time wasted in storing and retrieving the previous primes in part (7) negate any advantage that it has with having to actually make less divisions??
Or, does part (6), make up for having to make more computations with the fact that it only has to store very few variables??
Or even, is (5) faster than (6)?? Or is (d) faster than (e)

So far, the fastest combinatin i have made, (probably not the fastest, due to my lack of skill in C++ programming) is this:

N.B. this is just the source, you'll have to compile it yourself (or just read it in notepad) :)

[bugzpodder]

just a comment since its pretty interesting to see some of the methods that is presented by sql_lall.

let me add that 6k+/-1, and 30K +1,7,11,13,17,19,23,29 does NOT guarentee the number to be a prime. but if the number is actually in the format of the former or latter, it has a good chance of been a prime. If it doesn't work and its a prime, it's probably b/c its 2, 3, and 5. (5 is only applicable to the second case) these number are obtained by multipling the first n primes. 2*3=6.
both methods that eleminates non-primes work under the same reason (and the 210k one that i didn't mention):

lets take 30K+2 for example: obviously, you can factor out a 2 => 2(15K+1). obviously since 2 is a factor, it is NOT a prime. and so on with 30K+3, 30K+4 ...

of course, there are exceptions to this rule as mentioned b4: if k=4, 4*6 +1=25, which is a non prime. if k=13,13*6+1=49, which is also a non-prime. notice that the value of k used, 4, which is a non-prime, and 13 which is a prime itself.

another interesting fact is that these numbers relate heavily to a proof that there is infinate number of primes:

assume the largest prime is k, and all the primes in the world are:

2,3,5,7,11,...,k

let p=2*3*5*7*11*...*k+1. but none of the primes 2,3,5,7,11,...,k can divide into p, making p is prime. (notice p is the product of ALL the prime b4 it, each used once, 4*16+1, 13*6+1 are not) it uses the same idea at least.

[jhermiz]

Better yet we can devise a method using Erosthansis Seive's algorightm for finding exact primes. This was one of the quickest methods for finding a prime...and you are guaranteed to find a 'p' such that 'p' is a prime in a considerable amount of time. You need not test values > sqrt(p) in fact there is an algorthim using Seive's which can find primes based on j*j. Which at times is a lot less than the sqrt(j). Although the subject matter doesn't seem that difficult when one thinks about what a "prime" actually is.

Prime: An integer which can only be divisible by itself and one.

Not difficult to read and understand the difficulty comes when we base an algorthim on prime numbers. Some of the methods by SQL_ALL work...some don't because they don't guarantee accuracy. Some are quick...but again some are very slow and in fact the run time efficiency grows based on the number of multiplications/divisions/additions/subtractions.

Jon

[sql_lall]

I'm sorry if i didn't say it clearly, i have a habit of diong that:

What a mean with 1-7 and a-e is that you use them together.

i.e. 5 with d:
To test for primes < n
-Print 2,3,5
-make i the numbers (30K +1,7,11,13,17,19,23,29) <n
-divide i by every number (30K +1,7,11,13,17,19,23,29) <sqrt(i)
-If it divisible by none of these, print i
-next i

This way, 121 (30 *(4) + 1) is divided by 11 (30 *(0) + 11), and is not prime.

(This is what i have used in the diffp.cpp file. BTW, has anyone tried/timed it, or would people prefer the .exe file?)

[bugzpodder]

instead of dividing by all the numbers up to sqrt(i), you divided by the numbers you guarentees to include all the primes! thats a neat trick! btw as you yourself mentioned, you don't have to stick with 30, you could go with 6 and later 210. so what i am suggesting is that you could make it dynamic (say when i passes 210, you use 210K + 1,11,...)

[DavidHooper]

I seem to remember we established in that link I posted at the top that it becomes inefficient to continually lengthen the list bugzpodder. Maybe someone could test to find the optimum length...