Howdy, Stranger!

It looks like you're new here. If you want to get involved, click one of these buttons!

Categories

Prime number program problem

Hello,

My program has to determine if a number that I enter is a prime number - which I believe I have done. But if the number is not a prime number, it should tell me the highest divisor of this particular number. At the moment, my program gives all the divisors if the number is not a prime. And the input range must be between 1 and MAXINT. Can anyone tell me how to get MAXINT? how to declare it?

Thanks

[code]
#include
#include

void main()
{
char your_name[12];
int number;
int i;
int remainder;
int not_divisible = 1;

printf("Hello!, please enter your name: ");
scanf("%s", your_name);
printf("Enter a number: ");
scanf("%d", &number);

printf("
The number you entered is: %d", number);
printf("
");

for( i = 2; i < 10; i++ )
{
remainder = number % i;
if(remainder == 0 )
{
not_divisible = 0;
printf("This number is divisible by %d", i);
printf(" and it is not a prime number");
}
}
if(not_divisible == 1) printf("This a prime number!");
printf("
");
printf("Good-bye %s", your_name);
printf("
");
system("pause");
}
[/code]

Comments

  • LundinLundin Member Posts: 3,711
    : Hello,
    :
    : My program has to determine if a number that I enter is a prime number - which I believe I have done. But if the number is not a prime number, it should tell me the highest divisor of this particular number. At the moment, my program gives all the divisors if the number is not a prime. And the input range must be between 1 and MAXINT. Can anyone tell me how to get MAXINT? how to declare it?
    :
    : Thanks
    :
    : [code]
    : #include
    : #include
    :
    : void main()
    : {
    : char your_name[12];
    : int number;
    : int i;
    : int remainder;
    : int not_divisible = 1;
    :
    : printf("Hello!, please enter your name: ");
    : scanf("%s", your_name);
    : printf("Enter a number: ");
    : scanf("%d", &number);
    :
    : printf("
    The number you entered is: %d", number);
    : printf("
    ");
    :
    : for( i = 2; i < 10; i++ )
    : {
    : remainder = number % i;
    : if(remainder == 0 )
    : {
    : not_divisible = 0;
    : printf("This number is divisible by %d", i);
    : printf(" and it is not a prime number");
    : }
    : }
    : if(not_divisible == 1) printf("This a prime number!");
    : printf("
    ");
    : printf("Good-bye %s", your_name);
    : printf("
    ");
    : system("pause");
    : }
    : [/code]
    :

    If you mean that "MAXINT" is the largest possible value for an integer, then use the constant INT_MAX located in (or use UINT_MAX for unsigned int).

    It should be around 2.1 million on a 32-bit compiler (Windows) and 32767 on a 16-bit compiler (DOS).
  • JanusJanus Member Posts: 22
    : It should be around 2.1 million on a 32-bit compiler (Windows) and 32767 on a 16-bit compiler (DOS).
    :

    Close, but it is arround 2,147,483,648 (2.1 Billion) only if the integer is unsigned.

    Just to make sure: you are aware of the fact that your program will only check if the number is divisible by 2 to 10. That might not cut it, if you are checking numbers as large as 4 billion. I thought I point this out, but I am sure you knew that.

    Your code can be quite time consuming, so here is a hint to optimize it a bit more: The loop will only need to count up to 'floor(sqrt(number))+1'. If you do not understand why, do not implement it in your program. It would look like:

    for( i = 2; i < floor(sqrt(number))+1; i++ )
    : {
    : remainder = number % i;
    : if(remainder == 0 )
    : {
    : not_divisible = 0;
    : printf("This number is divisible by %d", i);
    : printf(" and it is not a prime number");
    : }
    : }

  • LundinLundin Member Posts: 3,711
    [b][red]This message was edited by Lundin at 2004-8-24 23:25:11[/red][/b][hr]
    : : It should be around 2.1 million on a 32-bit compiler (Windows) and 32767 on a 16-bit compiler (DOS).
    : :
    :
    : Close, but it is arround 2,147,483,648 (2.1 Billion) only if the integer is unsigned.


    Oops, that is what I ment. 2.1 billion for (signed) int, 4.3 billion for unsigned int.


  • rollerolle Member Posts: 115
    [green]It is a waste of time to test for even numbers - except for 2 of course.[/green]
  • JanusJanus Member Posts: 22
    : [green]It is a waste of time to test for even numbers - except for 2 of course.[/green]
    :

    Yeah, that should chop the big O in half. I completely forgot about it.

  • VilanyeVilanye Member Posts: 684
    [b][red]This message was edited by Vilanye at 2004-8-27 13:39:47[/red][/b][hr]
    The largest unique number that the original value can be divided into is sqrt(val). To be on the safe side I add one to the result.

    So if you are looking for prime numbers up to 1,000,000 for example you don't need to check for any number greater then 1001.

    That will optimize the code even further.


    : : [green]It is a waste of time to test for even numbers - except for 2 of course.[/green]
    : :
    :
    : Yeah, that should chop the big O in half. I completely forgot about it.
    :
    :



  • globalprogglobalprog Member Posts: 67
Sign In or Register to comment.