whether number is prime or not

This is a discussion on whether number is prime or not within the C Programming forums, part of the General Programming Boards category; If the number is greater than 2^32(4294967296)then how to determine whether is it prime or not? Ex:Is 4437864713 a prime ...

  1. #1
    Registered User
    Join Date
    Jan 2011
    Posts
    10

    whether number is prime or not

    If the number is greater than 2^32(4294967296)then how to determine whether is it prime or not? Ex:Is 4437864713 a prime number ?

  2. #2
    and the hat of wrongness Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    32,452
    Type "prime number algorithm" into google.
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.
    I support http://www.ukip.org/ as the first necessary step to a free Europe.

  3. #3
    Bit Fiddler
    Join Date
    Sep 2009
    Posts
    67
    Use long long or __int64.

  4. #4
    Registered User
    Join Date
    Jan 2011
    Posts
    10
    @Salem : I know the algo of the problem but main problem is how to handle the large number.As we can't use double data type cause we need to use % operator.

    Can any provide me a little code snippet for handling large number(>4294967296) and we can use % operator too with the number.

  5. #5
    and the hat of wrongness Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    32,452
    Well if a 64-bit type isn't an option, then try a bignum library like The GNU MP Bignum Library

    Or roll your own equivalent, if you're only interested in a few specific operations.
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.
    I support http://www.ukip.org/ as the first necessary step to a free Europe.

  6. #6
    Bit Fiddler
    Join Date
    Sep 2009
    Posts
    67
    Code:
    unsigned long long number = 0x7FFFFFFFFFFFFFFF;
    
    printf("%lld\n", number);

  7. #7
    Banned
    Join Date
    Aug 2010
    Location
    Ontario Canada
    Posts
    9,547
    Quote Originally Posted by amite View Post
    @Salem : I know the algo of the problem but main problem is how to handle the large number.As we can't use double data type cause we need to use % operator.

    Can any provide me a little code snippet for handling large number(>4294967296) and we can use % operator too with the number.
    Unless your compiler is an antique, it has a 64 bit integer type.

    Check your docs... Different comiplers implement 64 bit integers in different ways.
    It might be one of...

    1) unsigned long long int
    2) #include <stdint.h> then use uint64_t
    3) unsigned long int

    The easiest way to tell is to try different combinations and use sizeof() ... a 64 bit int will return 8 instead of 4.

  8. #8
    Registered User
    Join Date
    Jan 2011
    Posts
    10
    Quote Originally Posted by Fader_Berg View Post
    Code:
    unsigned long long number = 0x7FFFFFFFFFFFFFFF;
    
    printf("%lld\n", number);
    the number i have is 600851475143.
    unsigned long long number=600851475143;
    Even this satement give error.When i use 600851475 then it give the result.

  9. #9
    Registered User
    Join Date
    Jan 2011
    Posts
    10
    Quote Originally Posted by Fader_Berg View Post
    Code:
    unsigned long long number = 0x7FFFFFFFFFFFFFFF;
    
    printf("%lld\n", number);
    the number i have is 600851475143.
    unsigned long long number=600851475143;
    Even this satement give error.When i use 600851475 then it give the result.I am using codeblock on windows.

  10. #10
    Banned
    Join Date
    Aug 2010
    Location
    Ontario Canada
    Posts
    9,547
    Try...

    Code:
    #include <stdio.h>
    #include <stdint.h>
    
    int main (void)
     { uint64_t x;
    
        x = 600851475143; 
    
        printf("%lld", x );
        
        return 0;
         }

  11. #11
    and the hat of wrongness Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    32,452
    > When i use 600851475 then it give the result.I am using codeblock on windows.
    Then unfortunately, you HAVE to use the non-portable Microsoft conversion formats.
    Format Specification Fields: printf and wprintf Functions (CRT)

    Although the compiler is GCC, the 'C' run-time library is from Microsoft, so you get all the bugs/features of that library.

    One of the "bugs" being very poor support for C99 types.
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.
    I support http://www.ukip.org/ as the first necessary step to a free Europe.

  12. #12
    Banned
    Join Date
    Aug 2010
    Location
    Ontario Canada
    Posts
    9,547
    Quote Originally Posted by Salem View Post
    > When i use 600851475 then it give the result.I am using codeblock on windows.
    Then unfortunately, you HAVE to use the non-portable Microsoft conversion formats.
    Format Specification Fields: printf and wprintf Functions (CRT)

    Although the compiler is GCC, the 'C' run-time library is from Microsoft, so you get all the bugs/features of that library.

    One of the "bugs" being very poor support for C99 types.
    No SH_T... I just compared headers between VC++ and PellesC... The phrase "Gross Omission" comes to mind... By comparison VC++ is only about half there...

    I wonder... can I exchange headers and libs between them?
    Last edited by CommonTater; 01-26-2011 at 03:56 PM.

  13. #13
    Registered User
    Join Date
    Jan 2011
    Posts
    10
    Quote Originally Posted by Fader_Berg View Post
    Code:
    unsigned long long number = 0x7FFFFFFFFFFFFFFF;
    
    printf("%lld\n", number);
    Quote Originally Posted by CommonTater View Post
    Try...

    Code:
    #include <stdio.h>
    #include <stdint.h>
    
    int main (void)
     { uint64_t x;
    
        x = 600851475143; 
    
        printf("%lld", x );
        
        return 0;
         }
    I tried the following on windows(codeblock) and linux(gcc) :
    Code:
    #include <stdio.h>
    #include <stdint.h>
    int main()
    {
            uint64_t x;
            unsigned long long y;
            unsigned long int z;
            printf("%d\n",sizeof(x));
            printf("%d\n",sizeof(y));
            printf("%d\n",sizeof(z));
            return 0;
    }
    Results in both case are same :
    8
    8
    4

    but when i try to assign value 600851475143 to x or y then i get compile time error as :
    error : integer constant is too large for "long" type
    that's my problem when why compiler show such error while the number is too short than 2^64.
    One more thing long is expected to have size of 8 byte but here we get 4 byte ,why?

  14. #14
    Password:
    Join Date
    Dec 2009
    Location
    NC
    Posts
    587
    Use a bignum library. Bignum libraries allow you to use arbitrarily large numbers. For Linux, use GMP. For Windows, I prefer iMalc's library. You can get GMP through your distro's package management system. You can get iMalc's library at his website, Useful classes, you want BigInt or VarBigInt.
    Last edited by User Name:; 01-26-2011 at 08:08 PM.

  15. #15
    Banned
    Join Date
    Aug 2010
    Location
    Ontario Canada
    Posts
    9,547
    Quote Originally Posted by amite View Post
    I tried the following on windows(codeblock) and linux(gcc) :
    Code:
    #include <stdio.h>
    #include <stdint.h>
    int main()
    {
            uint64_t x;
            unsigned long long y;
            unsigned long int z;
            printf("%d\n",sizeof(x));
            printf("%d\n",sizeof(y));
            printf("%d\n",sizeof(z));
            return 0;
    }
    Results in both case are same :
    8
    8
    4

    but when i try to assign value 600851475143 to x or y then i get compile time error as :


    that's my problem when why compiler show such error while the number is too short than 2^64.
    One more thing long is expected to have size of 8 byte but here we get 4 byte ,why?
    long is generally only 32 bits... you need long long to get 64.

    That doesn't make any sense... your number is only 39bits... there's no reason it won't fit in a uint64_t ... unless your compiler is all messed up... Did you try this both on Windows and Linux?

    It works here on both VC++ (with my re-worked header file) and on PellesC ....

Page 1 of 2 12 LastLast
Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Simple XOR Program
    By dolfaniss in forum C Programming
    Replies: 8
    Last Post: 05-24-2010, 01:27 PM
  2. Prime number example
    By Johnathan1707 in forum C Programming
    Replies: 2
    Last Post: 07-26-2009, 12:40 PM
  3. xor linked list
    By adramalech in forum C Programming
    Replies: 23
    Last Post: 10-14-2008, 10:13 AM
  4. Prime Factor Fxn
    By alpha in forum C++ Programming
    Replies: 2
    Last Post: 10-21-2003, 10:44 AM
  5. Replies: 3
    Last Post: 01-14-2003, 09:34 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21