Programming newfag here. I'm trying to make a c program that determines whether a number is prime. It isn't working properly though. It only indicate that the number is not prime, regardless of the number, so something wrong. Anybody can help?
#include<stdio.h>
int main(void)
{
int number;
int count;
int divisor = 2;
printf("Input number for primality testing\n");
scanf("d",number);
while (divisor < number/2) {
if (number % divisor == 0) {
break;
}
else
divisor++;
}
if (divisor == number/2) {
printf("Number is prime\n");
}
else {
printf("Number is not prime\n");
}
return 0;
}
You want if (divisor > number/2) to check if no divisor was found. The last divisor++ will make it greater than number/2. At the moment, only the number 4 will be counted as prime (it's divisible by two, and 2 == 4/2 satisfies the condition).
Name:
Anonymous2008-09-25 14:36
Thanks, i'll try now
Name:
Anonymous2008-09-25 14:40
Thanks for the effort, I understand what you mean, but it not working. I used some printf's and found that the program never reach the else to increment the divisor. I still don't know why?
also while we're at it, read up on the sieve of eratosthenes. you don't need to go to n/2, you've reached the end at n^(1/2), and also you can get rid of many of the divisors as nonprime while going through them.
Name:
Anonymous2008-09-25 15:43
This is much better, thanks for the n^(1/2) tip, makes it a bit faster. The program works now, although only for numbers up to 2^32. Heres the code now. The if statement at the end seems kind of messy, but it works.
#include<stdio.h>
int main(void)
{
unsigned int number;
unsigned int divisor = 2;
printf("Input number for primality testing (max 4294967295)\n");
scanf("%d",&number);
while (divisor < number^(1/2)) {
if (number % divisor == 0) {
break;
}
else {
divisor++;
}
}
if ((divisor == number^(1/2) && number != 4)
|| number == 2 || number == 3) {
printf("Number is prime\n");
}
else {
printf("Number is not prime\n");
}
return 0;
}
long m = sqrt(n);
try {
for(long i=2; i < m; i++)
if(n % i == 0)
throw "Number is not prime";
} catch (char * no) {
std::cout << no << std::endl;
return;
}
int main (int argc, char ** argv) {
long int a;
mpz_t b;
printf("Input number for primality testing\n");
scanf("%ld", &a);
mpz_init_set_si(b, a);
switch (mpz_probab_prime_p(b, 8)) {
case IS_PRIME:
printf("%ld is prime.\n", a);
break;
case MAYBE_PRIME:
printf("%ld might be prime.\n", a);
break;
case NOT_PRIME:
printf("%ld is not prime.\n", a);
break;
default:
printf("What.\n");
}
mpz_clear(b);
return 0;
}
implementing primality tests is boring, let's go shopping.
Name:
Anonymous2008-09-26 1:16
Now that I think of it, yo /prog/ what is the fastest primality test currently?
>>34
no, it's because mpz_probab_prime_p isn't what you should use if you really want to know if a number is prime.
what's you're excuse for ignoring mpz_inp_str/mpz_out_str and limiting the input to what can fit in a long int?