10 Replies - 9738 Views - Last Post: 08 August 2010 - 07:17 PM Rate Topic: -----

#1 tscott  Icon User is offline

  • D.I.C Regular

Reputation: 2
  • View blog
  • Posts: 370
  • Joined: 30-January 09

Java code to check if a number is Prime

Posted 07 August 2010 - 11:50 AM

I know that the rule for prime is that the # can't be divisible by anything other then itself and 1. i.e. 5 / 2 = 2, 5 / 3 = 1, so we know that 5 is prime because only 5 x 1 can get us 5 so in writing java code lets say we have an array which is size n with numbers inside. And we wanted to check if each of those numbers were prime, and count how many were. Lets assume the array is called A and has n # of elements inside of it
int count = 0; 
for(int i = 1; i <a.length; i++)
{   if(A[i] % 2 = 1)
    count++;
}
return count;



Would this work?

Is This A Good Question/Topic? 0
  • +

Replies To: Java code to check if a number is Prime

#2 Cuzzie  Icon User is offline

  • D.I.C Regular
  • member icon

Reputation: 72
  • View blog
  • Posts: 341
  • Joined: 16-July 10

Re: Java code to check if a number is Prime

Posted 07 August 2010 - 12:12 PM

Your code is messed up. What's the name of your array? Is it "a" or "A"? Java is case-sensitive, so be careful with variables' names. And, your condition in if statement is wrong either. If you want to compare whether the value of a[i] % 2 is 1 or not, you should use == instead of =. = is only used for assigning values to variables. The algorithm you're using can only be used to check whether the value of the variable is an odd number or even number. For prime number checking algorithms, you might wanna try Sieve of Erasthosthenes or Sieve of Atkin.
Was This Post Helpful? 0
  • +
  • -

#3 Tapas Bose  Icon User is offline

  • D.I.C Regular
  • member icon

Reputation: 23
  • View blog
  • Posts: 472
  • Joined: 09-December 09

Re: Java code to check if a number is Prime

Posted 07 August 2010 - 12:19 PM

I guess not. I think the definition of prime is clear to you. Prime is a number which is divisible only by 1 and itself. That means moduler division of given number and any other number less than that will give you a non-zero integer. Here it is Prime number.
5 is a prime number because :
5%2!=0;
5%3!=0;
5%4!=0;
So you have an array of numbers. Define a function say isPrime(), pass each of the number into that function. Write for loop which iterate from 2 to that number and check weather or not that number gives 0 on moduler division with number less than it. If the mod is 0 then break the loop and mark it as composite. Now the numbers in the array that are not composite is prime.
Although the time complexity is highest for this test. If you traverse upto sqrt(n) this will minimize you time requirement and sqrt(n) is sufficient limit for primality checking. Although there are many other algorithms.
Try it.
Thank you.
Was This Post Helpful? 0
  • +
  • -

#4 bcranger  Icon User is offline

  • D.I.C Lover
  • member icon

Reputation: 252
  • View blog
  • Posts: 1,199
  • Joined: 01-February 10

Re: Java code to check if a number is Prime

Posted 07 August 2010 - 12:21 PM

It would not work. Counterexample:

21 % 2 == 1...btw you need two "==" in your if statement.
21 IS NOT PRIME

:D
Was This Post Helpful? 0
  • +
  • -

#5 tscott  Icon User is offline

  • D.I.C Regular

Reputation: 2
  • View blog
  • Posts: 370
  • Joined: 30-January 09

Re: Java code to check if a number is Prime

Posted 07 August 2010 - 12:24 PM

I've seen this article but it doesn't show any where how to write java for it. I just need a quick solution I can study for a java final something simple thats all I'm looking for its sad he is having us memorize such a stupid procedure to begin with for an algorithms class
Was This Post Helpful? 0
  • +
  • -

#6 Tapas Bose  Icon User is offline

  • D.I.C Regular
  • member icon

Reputation: 23
  • View blog
  • Posts: 472
  • Joined: 09-December 09

Re: Java code to check if a number is Prime

Posted 07 August 2010 - 12:25 PM

I think implementation of Sieve of Atkin is harder than Sieve of Erathosthenes. Normal implementation of Sieve of Atkin which is shown in wiki link gives slower generation of prime than that of Sieve of Eratosthenes. Also Sieve of Eratosthenes is good for number less than 10,000,000,000. But there is a chance of getting memory error if you try this huge range, without taking any remedial measure.
Was This Post Helpful? 0
  • +
  • -

#7 adhish94  Icon User is offline

  • New D.I.C Head
  • member icon

Reputation: 4
  • View blog
  • Posts: 45
  • Joined: 12-July 10

Re: Java code to check if a number is Prime

Posted 08 August 2010 - 05:35 AM

For checking a number for being prime, you know the concept but can't implement it properly. Dry-run the code in your mind once, and you'll get what I mean. See, you are dividing each element of the array by 2 and increasing the counter if it is. So, the counter actually counts the number of even numbers in the program.

Therefore, you should run another loop nested inside this loop. The outer loop (say, i loop) runs from 0 to a.length - 1 (because indexing starts from 0), while the inner loop (say, j loop) from 1 to a[i]. Hence, for every element, it will run from 1 to that element, and the counter will increase if the element is divisible by any number lying in between 1 and that number. Outer the inner loop (but still inside the outer loop) print a[i] if the counter is true.

I guess using A instead of a in the condition is just a typo, because remember Java is a case-sensitive language. And also remember if you use the = operator in the condition, it will almost always be true as it will set the value of that variable to something. So, use ==, which is for checking.

If you still have problems implementing the logic, I might help again. :)

This post has been edited by adhish94: 08 August 2010 - 05:43 AM

Was This Post Helpful? 1
  • +
  • -

#8 adhish94  Icon User is offline

  • New D.I.C Head
  • member icon

Reputation: 4
  • View blog
  • Posts: 45
  • Joined: 12-July 10

Re: Java code to check if a number is Prime

Posted 08 August 2010 - 05:55 AM

And don't memorize stuff, especially programming code. You should build your own logic. A good way to start is to first pen down an algorithm and then try implementing it.
Was This Post Helpful? 1
  • +
  • -

#9 Mercurial  Icon User is offline

  • D.I.C Head

Reputation: 18
  • View blog
  • Posts: 178
  • Joined: 06-November 09

Re: Java code to check if a number is Prime

Posted 08 August 2010 - 06:36 AM

View Posttscott, on 07 August 2010 - 10:50 AM, said:

int count = 0; 
for(int i = 1; i <a.length; i++)
{   if(A[i] % 2 = 1)
    count++;
}
return count;



Would this work?

First off
if(A[i] % 2 == 1)
This modified line says: Is value of the array an odd number(1,3,5,7,9... 2k+1)? if yes: count++. So, it wont work. What you should do is:
for(int i = 0; i <a.length; i++)
Every array starts with an element 0, not 1.
if(Prime(A[i])==true) count++; 
If A[i] is indeed a prime number, increment the count var. And the last piece of code, the Prime function:
boolean Prime(int number){
//Check if number is a prime number
// return true/false;
}


Was This Post Helpful? 0
  • +
  • -

#10 Luckless  Icon User is offline

  • </luck>
  • member icon

Reputation: 293
  • View blog
  • Posts: 1,146
  • Joined: 31-August 09

Re: Java code to check if a number is Prime

Posted 08 August 2010 - 07:41 AM

It's as simple as starting with the number in question then setting up a for loop to run from the number in question down to 1.
you have to check if the number in question is divisible by any number between itself and 1, otherwise, your data is not complete
Was This Post Helpful? 0
  • +
  • -

#11 pbl  Icon User is offline

  • There is nothing you can't do with a JTable
  • member icon

Reputation: 8347
  • View blog
  • Posts: 31,913
  • Joined: 06-March 08

Re: Java code to check if a number is Prime

Posted 08 August 2010 - 07:17 PM

View PostTapas Bose, on 07 August 2010 - 01:25 PM, said:

I think implementation of Sieve of Atkin is harder than Sieve of Erathosthenes. Normal implementation of Sieve of Atkin which is shown in wiki link gives slower generation of prime than that of Sieve of Eratosthenes. Also Sieve of Eratosthenes is good for number less than 10,000,000,000. But there is a chance of getting memory error if you try this huge range, without taking any remedial measure.

Actually it is 2,xxx,xxx,xxx
Here is a solution to avoid that problem
http://www.dreaminco...snippet4665.htm
:D
Was This Post Helpful? 1
  • +
  • -

Page 1 of 1