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?
ANG (ANG's Not GNU (ANG's Not GNU's Not GNU's Not UNIX (ANG's Not GNU's Not GNU's Not UNIX's Not GNU's Not UNIX's Not UNIX (ANG's Not GNU's Not GNU's Not UNIX's Not GNU's Not UNIX's Not UNIX's Not GNU's Not UNIX's Not UNIX's Not UNIX (ANG's Not GNU's Not GNU's Not UNIX's Not GNU's Not UNIX's Not UNIX's Not GNU's Not UNIX's Not UNIX's Not UNIX's Not GNU's Not UNIX's Not UNIX's Not UNIX's Not UNIX)))))
when the pedobear icon is clicked, have Ash Ketchum pop on screen and say PEDOBEAR! I CHOOSE YOU! and pokeball thrown etc etc and the pedobear icon grows in size as the wipe progresses. win?