Jump to content
xisto Community
Sign in to follow this  
alamzaib

How I Shall Scan Prime Numbers.. that is 1,3,5,7,11,13,17,19...

Recommended Posts

I want to scan prime numbers ,have you logic to solve this problem?

 

here is example of even numbers:

--------------------------------------------------------------------------------------------------------------void main (void){clrscr();int a;printf("input any no.");scanf("%d"&a);if(a%2=0){printf("the number is even");getch();}------------------------------------------------------------------------------------------------------------
Now I want to scan prime numbers and I dont have logic please help me to solve my problem.

thanks in advance. :P

 

Notice from serverph:
added code tags... please use appropriate code tags as needed. thanks.

Share this post


Link to post
Share on other sites

The only logic I can think of is to divide the number by all numbers up to the square root of the original number and check the modulus of each one. So, get the number from the user. Then do the floor of the square root of that number. This is the highest value you need to divide by. Then create a loop, starting with that divisor, decreasing by one each time, stopping when it is equal to 1. Get the modulus of the number divided by the divisor. If at any point you get a 0 value, end the loop and output that the number is not prime. If it finishes with no 0 values then the number must be prime.

Sorry, I don't know enough C to write the code, but I could do it in Java if you could sort of translate from that?

int num; //The number from the userint divisor = Math.floor(Math.sqrt(num)); //Our largest divisorif (num == 2)	return true;else if (num < 2)	return false;for (i = 2; i <= divisor; i++) {	if (num % i == 0)		return false;}return true;

If it needs more explaining (which it probably does :P ) then feel free to ask.

Share this post


Link to post
Share on other sites

rvalkass is basically right, just divide your test number by every prime number up till the square root of the test number, and if none of them make an even division, the test number is prime. Of course, use some common sense in doing this. Don't waste time testing even numbers, and use algorithms like the digits of x add up to a multiple of 3 if x is divisible by 3 and so on. Remember, division is the lengthiest common arithmetic process to do. If you want your 'scan' to go faster, you'll need better algorithms.

int divisor = Math.floor(Math.sqrt(num)); //Our largest divisor
Lol. That's about the only thing you might need a little help translating to C/C++.
If you're using C, look up the <math> header, if C++, look up <cmath> on the internet.
A little work won't kill ya. :P

Share this post


Link to post
Share on other sites

The only logic I can think of is to divide the number by all numbers up to the square root of the original number and check the modulus of each one. So, get the number from the user. Then do the floor of the square root of that number. This is the highest value you need to divide by. Then create a loop, starting with that divisor, decreasing by one each time, stopping when it is equal to 1. Get the modulus of the number divided by the divisor. If at any point you get a 0 value, end the loop and output that the number is not prime. If it finishes with no 0 values then the number must be prime.
Sorry, I don't know enough C to write the code, but I could do it in Java if you could sort of translate from that?

int num; //The number from the userint divisor = Math.floor(Math.sqrt(num)); //Our largest divisorif (num == 2)	return true;else if (num < 2)	return false;for (i = 2; i <= divisor; i++) {	if (num % i == 0)		return false;}return true;

If it needs more explaining (which it probably does :D ) then feel free to ask.



Okay :D

but I have to use only "if-else" statement not "for" statement.Have you any tips ?
:P

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now
Sign in to follow this  

×
×
  • Create New...

Important Information

Terms of Use | Privacy Policy | Guidelines | We have placed cookies on your device to help make this website better. You can adjust your cookie settings, otherwise we'll assume you're okay to continue.