 How I Shall Scan Prime Numbers.., that is 1,3,5,7,11,13,17,19... |
|
|
|
|
  |
  Feb 15 2007, 03:59 PM
Post
#1
|
|
|
Newbie [Level 1]  Group: Members Posts: 18 Joined: 7-February 07 Member No.: 38,392  |
I want to scan prime numbers ,have you logic to solve this problem?
here is example of even numbers: CODE -------------------------------------------------------------------------------------------------------------- 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. 
Reason for edit: see moderator notes
|
 |
 
|
|
Feb 15 2007, 07:36 PM
Post
#2
|
|
|
apt-get moo  Group: [MODERATOR] Posts: 1,920 Joined: 28-May 05 From: Hertfordshire, England Member No.: 7,593  |
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? CODE int num; //The number from the user int divisor = Math.floor(Math.sqrt(num)); //Our largest divisor if (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  ) then feel free to ask.
|
|
|
|
|
Feb 19 2007, 11:53 PM
Post
#3
|
|
|
Super Member Group: Members Posts: 380 Joined: 14-November 04 From: Elysium Member No.: 2,280 |
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.
CODE 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. 
|
|
|
|
|
Feb 25 2007, 05:23 PM
Post
#4
|
|
|
Newbie [Level 1] Group: Members Posts: 18 Joined: 7-February 07 Member No.: 38,392 |
QUOTE(rvalkass @ Feb 15 2007, 07:36 PM)  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? CODE int num; //The number from the user int divisor = Math.floor(Math.sqrt(num)); //Our largest divisor if (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 ) then feel free to ask.Okay but I have to use only "if-else" statement not "for" statement.Have you any tips ? 
|
|
|
|
|
Mar 3 2007, 02:53 PM
Post
#5
|
|
|
Newbie [Level 1] Group: Members Posts: 18 Joined: 19-February 07 Member No.: 38,888 |
I think a loop would be needed , unless you have a function like this :
CODE boolean isPrime (int num,int divisor){
if (num % divisor == 0) return false; if (num / 2 < divisor ) return true; else isPrime(num,++divisor); } This post has been edited by Jdeveloper: Mar 5 2007, 06:34 AM |
|
|
|
|
Similar Topics
| Topics | Topics | |
|---|---|---|
|
|
|
|
Lo-Fi Version | Time is now: 16th May 2008 - 06:07 PM |