Thread: Prime number problem (please help)

the prime numbers from 1 to 2500 can be obtained as follows. From a list of the numbers of 1 to 2500,cross out al multiples of 2(but not 2 itself)Then, find the next number (n, say) that is not crossed out and cross out all multiples of n (but not
including n). Repeat this last step provided that n has not exceeded 50 (the square
root of 2500). The numbers remaining in the list (except 1) are prime. Write a
program which uses this method to print all primes from 1 to 2500. Store your
output in a file called primes.out.


Can someone please tell me how to go about doing this?

There are several algorithms on the 'net that describe how to find prime numbers. Google 'java prime numbers', 'sieve of Eratosthenes', 'euler prime numbers', or similar.

I am not insulting you here but here are just a few questions:

1.) Do you how to figure how prime numbers?
2.) Figure it out on a piece of paper first, do 1-25 for example.
3.) Post some code and we will help you out, but I am feeling nice and will give you a nice push in the right direction....

//checks whether an int is prime or not.
boolean isPrime(int n) {
    for(int i=2;2*i<n;i++) {
        if(n%i==0)
            return false;
    }
    return true;
}

Originally Posted by jocdrew21

I am not insulting you here but here are just a few questions:

1.) Do you how to figure how prime numbers?
2.) Figure it out on a piece of paper first, do 1-25 for example.
3.) Post some code and we will help you out, but I am feeling nice and will give you a nice push in the right direction....

//checks whether an int is prime or not.
boolean isPrime(int n) {
    for(int i=2;2*i<n;i++) {
        if(n%i==0)
            return false;
    }
    return true;
}

yes i already have that piece of code.I dont know how to get the list of numbers from 1 - 2500. And i dont understand the part about n exceeding 50 from the question.

This method is called Sieve of Eratosthenes.

1	2	3	4	5	6	7	8	9	10
11	12	13	14	15	16	17	18	19	20
21	22	23	24	25	26	27	28	29	30
31	32	33	34	35	36	37	38	39	40
41	42	43	44	45	46	47	48	49	50
51	52	53	54	55	56	57	58	59	60
61	62	63	64	65	66	67	68	69	70
71	72	73	74	75	76	77	78	79	80
81	82	83	84	85	86	87	88	89	90
91	92	93	94	95	96	97	98	99	100

The ones marked red are prime. For this method, an array is used (not this one, single dimensional). First, starting from after 2, every 2nd no. is crossed out. Then find out the smallest remaining no. >2, which is 3. So cross out every 3rd no. Now find smallest remaining no. >3 which is 5. So cross out every 5th no. This goes on till you have crossed out every no. divisible by [root of N] where [] stands for floor function. Use a 1D array for this. Good luck.

how do i get 2500 numbers into the array?

--- Update ---

Originally Posted by Abhilash

This method is called Sieve of Eratosthenes.

1	2	3	4	5	6	7	8	9	10
11	12	13	14	15	16	17	18	19	20
21	22	23	24	25	26	27	28	29	30
31	32	33	34	35	36	37	38	39	40
41	42	43	44	45	46	47	48	49	50
51	52	53	54	55	56	57	58	59	60
61	62	63	64	65	66	67	68	69	70
71	72	73	74	75	76	77	78	79	80
81	82	83	84	85	86	87	88	89	90
91	92	93	94	95	96	97	98	99	100

The ones marked red are prime. For this method, an array is used (not this one, single dimensional). First, starting from after 2, every 2nd no. is crossed out. Then find out the smallest remaining no. >2, which is 3. So cross out every 3rd no. Now find smallest remaining no. >3 which is 5. So cross out every 5th no. This goes on till you have crossed out every no. divisible by [root of N] where [] stands for floor function. Use a 1D array for this. Good luck.

this is what i have so far

 import java.util.*;
public class  Prime{
	public static void main (String [] args){
		Scanner in = new Scanner (System.in);
 
int [] primes = new int [2500];
 
	int num=1,i=0;
	while(num <= 2500){
		primes[i] = num;
		num ++;
		System.out.printf("%d\n",primes[i]);
	}	
}//end main
 
public static void sieve(int [] primes)
 
 
 
	}

How can i populate an array with numbers 1 to 2500???

Threads merged.

Originally Posted by Norm

Use a for loop containing an assignment statement.

for (int i=0;i <=2500; array[i] ++)

is that it??

Originally Posted by Norm

Try it and see what happens. Print the contents of the array using:
System.out.println("an ID "+ java.util.Arrays.toString(theArrayNameHere));
Recommend doing it for 25 elements vs 2500 for testing.

ok im making some progress with the problem.But im trying to output the results to a file however im getting an error.

	if(isPrime[i - 1]){
 			out.printf("%d",i);
 			out.println();

everything worked well before i tried to output the results to a file.
im getting an error at the two out.printf lines that says cannot find symbol.

Originally Posted by Norm

What symbol is not found?

idk it just says symbol not found. I made sure to close the file. However im not getting my data from an input file.It is populated into an array.Everything worked b4 i tried to print to a file. So im stuck

Originally Posted by Norm

That's a compiler error which means your code is not ready for execution. You need to find out what symbol is not found. Try using the javac command to compile the file. It gives nice error messages:
The error message shows the source with a ^ under the location of the error.
Here is a sample from the javac compiler:

TestSorts.java:138: cannot find symbol
symbol  : variable var
location: class TestSorts
         var = 2;
         ^

public static void Sieve(int n)throws IOException{
 
 	boolean [] isPrime = new boolean [n];
 	isPrime [0] = false;
 
 	for(int c=1;c <n; c++){
 		isPrime[c] = true;
 	}//end for
 	for(int i=2;i <=n;i++){
 		if(isPrime[i - 1]){
 			out.printf("%d",i);
 			out.println();
 		for(int j= i * i;j <=n;j+=i){
 			isPrime[j-1]=false;
 		}
 		}
 	}	
 }//end method
}//end class

thats my method. it says cannot find symbol
out.println();
^
symbol: variable out
location: class
2 errors

Process completed.

--- Update ---

the method works without the implementation of the output file. How can someone help me plz.How can i send the data to an output file

Originally Posted by Norm

Where is the variable: out defined? Is it in scope where the error happens?

no its defined in the main .
still getting the same error

Originally Posted by Norm

Please read post#19
Where is out defined?

class A_Class {
   int classVar; // define at class level;  in Scope for all methods
 
   void meth1() {
       int aVar;    // define aVar; in Scope only within meth1
       //  classVar in Scope here
       //...
   } // end meth1()
 
   void meth2() {
       //  aVar in NOT in SCOPE here
       //  classVar in Scope here
       //...
   } //  end meth2()
} // end class

Ok i did that and its saying expected. I dont know what else to do

Originally Posted by Norm

You need to copy the full text of the error message and paste it here. I can't see your code from here.

--------------------Configuration: <Default>--------------------
C:\Users\Desktop\Primes.java:32: error: <identifier> expected
out.close();
^
1 error

Process completed.