DrOmango Posted October 16, 2004 Share Posted October 16, 2004 (edited) for exercise,, how would i be able to write a function that will accept one integer parameter (greater than 3) and determin if that number is prime or not? how do i do that after declaring my variables? Edited October 16, 2004 by DrOmango Link to comment Share on other sites More sharing options...
0 kjordan2001 Posted October 16, 2004 Share Posted October 16, 2004 You would see if the modulo (a%b) is 0 where b is 2,3,5, and 7, if it is, it isn't prime. You use 2,3,5,7 since each other number under 10 (4,8,9) are multiples of these, and every other number that isn't prime should be divisible by these. Of course you'll want to check if it is one of those numbers since those are prime too. Link to comment Share on other sites More sharing options...
0 FiREFLi Posted October 16, 2004 Share Posted October 16, 2004 I just saw the title on the main page and thought yep, I've done that :D But not in vb.net it's in php. I'll post the code and feel free to asking porting questions. :) function is_prime($x) { $highestDenom=ceil(sqrt($x)); $prime=1; for($i=2; $i<=$highestDenom; $i++) { if($x%$i=="0") { $prime=0; } } if($prime) { print("$x is a prime"); } } Link to comment Share on other sites More sharing options...
0 kjordan2001 Posted October 16, 2004 Share Posted October 16, 2004 I just saw the title on the main page and thought yep, I've done that :D But not in vb.net it's in php. I'll post the code and feel free to asking porting questions. :) function is_prime($x) { $highestDenom=ceil(sqrt($x)); $prime=1; for($i=2; $i<=$highestDenom; $i++) { if($x%$i=="0") { $prime=0; } } if($prime) { print("$x is a prime"); } } 584743715[/snapback] Heh, I got rushing and forgot that my hint wouldn't work for prime numbers squared, that's a much better solution ;) Link to comment Share on other sites More sharing options...
0 DrOmango Posted October 16, 2004 Author Share Posted October 16, 2004 So its asking to write a function about verifying whether its a prime or not, then to list all the numbers before it that are prime. How do I go about doing this? For example, whats the math involved in calculating if a number is prime or not? Link to comment Share on other sites More sharing options...
0 kjordan2001 Posted October 16, 2004 Share Posted October 16, 2004 So its asking to write a function about verifying whether its a prime or not, then to list all the numbers before it that are prime. How do I go about doing this?For example, whats the math involved in calculating if a number is prime or not? 584743919[/snapback] fr3ak's post shows you the math you need. You go from 2 to sqrt(x) rounded up and if x%i, where i is from 2 to sqrt(x), equals 0, then it is not prime. However, if you get up to sqrt(x) rounded up and it doesn't even match, then your number is prime. Link to comment Share on other sites More sharing options...
0 DrOmango Posted October 16, 2004 Author Share Posted October 16, 2004 fr3ak's post shows you the math you need. You go from 2 to sqrt(x) rounded up and if x%i, where i is from 2 to sqrt(x), equals 0, then it is not prime. However, if you get up to sqrt(x) rounded up and it doesn't even match, then your number is prime. 584744109[/snapback] okay okay i got this! thank you kjordan2001 & fr3ak :) Link to comment Share on other sites More sharing options...
0 MrA Posted October 16, 2004 Share Posted October 16, 2004 fr3ak's post shows you the math you need.? You go from 2 to sqrt(x) rounded up and if x%i, where i is from 2 to sqrt(x), equals 0, then it is not prime.? However, if you get up to sqrt(x) rounded up and it doesn't even match, then your number is prime. 584744109[/snapback] Actually you only need to go from 2 to sqrt(x) rounded up and if x%i, where is a prime numberb> from 2 to sqrt(x), equals 0, then it is not prime. This makes it a bit harder, but much more efficient. Link to comment Share on other sites More sharing options...
0 kjordan2001 Posted October 16, 2004 Share Posted October 16, 2004 Actually you only need to go from 2 to sqrt(x) rounded up and if x%i, where i is a prime number from 2 to sqrt(x), equals 0, then it is not prime. This makes it a bit harder, but much more efficient. 584747522[/snapback] Eh? Not sure I understood that, but do you mean see if x%sqrt(x) is 0? If that's what you mean, that would be better. It would probably be better to go from sqrt(x) down to 2. Link to comment Share on other sites More sharing options...
0 Thinkz Posted October 17, 2004 Share Posted October 17, 2004 One quick calculation that can be used to speed things up before performing the full primality check on each number is to use Fermat's little theorem. This theorem states that a number p is prime if some number a, where a < p, raised to the power p-1 % p = 1. This check does not guarantee that your number p is prime when the result == 1, however, it can quarantee that if your final result != 1, your number p is not prime. This might come in useful if you are asked to determine the primality of some 40 digit integer. Rather than entering a loop for a very, very, long time, trying to determine primality, you can use fermat's theorem to quickly eliminate a large percentage of inputs. There are also some more robust primality testing algorithms, however learning the math required to implement these algorithms is probaly overkill for your project. Link to comment Share on other sites More sharing options...
0 Hal2k1 Posted October 17, 2004 Share Posted October 17, 2004 i just wrote this proggie a few hours ago in dev-cpp /* 5. Escreva uma fun??o em C que RECEBA COMO PAR?METRO um valor num?rico inteiro positivo e retorne verdadeiro caso este n?mero seja primo, e falso caso contr?rio. Implemente tamb?m uma fun??o main na qual o valor ? lido e que chame a fun??o implementada. */ #define VERDADEIRO 1 #define FALSO 0 #include <stdio.h> #include <stdlib.h> int primo (int n); void main (void){ int n; printf("\nNumero: "); scanf("%d",&n); if ( primo(n) == VERDADEIRO) printf("Numero primo "); else printf("Numero NAO primo "); getch(); } //****************************************************************************** //numero primo, divisivel apenas por 1 e pelo proprio. 1, 2, 3, 5, 7, 11. int primo (int n){ int retorno = VERDADEIRO; int i = 2; while(i<n){ //printf("\n %d %% %d = %d",n, i, n%i); if(n%i==0) retorno = FALSO; i++; } return retorno; } Link to comment Share on other sites More sharing options...
0 kjordan2001 Posted October 17, 2004 Share Posted October 17, 2004 One quick calculation that can be used to speed things up before performing the full primality check on each number is to use Fermat's little theorem. This theorem states that a number p is prime if some number a, where a < p, raised to the power p-1 % p = 1. This check does not guarantee that your number p is prime when the result == 1, however, it can quarantee that if your final result != 1, your number p is not prime.This might come in useful if you are asked to determine the primality of some 40 digit integer. Rather than entering a loop for a very, very, long time, trying to determine primality, you can use fermat's theorem to quickly eliminate a large percentage of inputs. There are also some more robust primality testing algorithms, however learning the math required to implement these algorithms is probaly overkill for your project. 584750911[/snapback] a^p-1 % p? Seems like a^p-1 could get very big very quickly, especially with the 40 digit type you're talking about, which could exceed the largest number an int can handle. Link to comment Share on other sites More sharing options...
0 MrA Posted October 18, 2004 Share Posted October 18, 2004 a^p-1 % p? Seems like a^p-1 could get very big very quickly, especially with the 40 digit type you're talking about, which could exceed the largest number an int can handle. 584756208[/snapback] If you were using a large number library, then the number of digits would be unimportant. For a lot of classical algebra problems, the int (or long, or long long) is just too small a data type. Try writing an RSA encryption program using the int data type. It would be useless since you would be able to find the nesessary primes in a split-second. Oh, and Thinkz said that a < p. It doesn't have to be. The condition on a is the it is not divisible by p. So p+1 is a valid a (for p > 2). Link to comment Share on other sites More sharing options...
0 Andareed Posted October 18, 2004 Share Posted October 18, 2004 There are math tricks you can apply for a^(p-1) % p. Link to comment Share on other sites More sharing options...
Question
DrOmango
for exercise,, how would i be able to write a function that will accept one integer parameter (greater than 3) and determin if that number is prime or not?
how do i do that after declaring my variables?
Edited by DrOmangoLink to comment
Share on other sites
13 answers to this question
Recommended Posts