Thread: Prime Numbers

  1. #1
    Registered User
    Join Date
    Nov 2001
    Posts
    241

    Lightbulb Prime Numbers

    I made a header file a while ago, that was meant to check if a number is prime. I attached it to this post, and I have a link to my page where I have a zip file with source code and a data file of the first million prime numbers. Let me know what you think of it.My Page

  2. #2
    A Banana Yoshi's Avatar
    Join Date
    Oct 2001
    Posts
    859

    Lightbulb Well done

    But I can do it in another way, without using the MATH.H include:

    void prime(int prime){
    int x=1;
    do{
    x++; // counter plus one
    }while(prime % x!=0); // use modulus to check
    if(prime == x){ //prime
    printf("Prime");
    }
    else if (prime != x){ // not prime
    printf("Not Prime");
    }
    return 0;
    }

    Hope this will be useful information.
    Yoshi

  3. #3
    Registered User
    Join Date
    Nov 2001
    Posts
    241
    I know I could have done it that way, but I was writing the code to be fairly fast because I used it to find the first million prime numbers. I use sqrt() because it is the largest number that could be divisble to the number. Prime numbers would keep the program running, and it would take longer.

  4. #4
    of Zen Hall zen's Avatar
    Join Date
    Aug 2001
    Posts
    1,007
    I think something like this would probably be quicker if you wanted the first million primes -

    Code:
    	bool pNumber[1000000];
    
    	memset(pNumber,1,1000000);
    
    	for(int i=2;i<1000000;i++)
    	{
    		if(pNumber[i]==true)
    		{
    			for (int j=i+i; j<1000000; j+=i)
    				pNumber[j]=false;
    		}
    	}
    zen

  5. #5
    Registered User
    Join Date
    Nov 2001
    Posts
    241
    no, I meant the first million prime numbers, not the prime numbers up to one million, and when you get into large arrays, you have to change the some stuff. My way would still be faster do to my variable that changes the step of my for loop, and it will determine whether any number is prime, not just the odd ones.

  6. #6
    of Zen Hall zen's Avatar
    Join Date
    Aug 2001
    Posts
    1,007
    Sorry, should have read it properly. However, there are some variations on the sieve that are efficient for generating the round about the first million primes.

    and it will determine whether any number is prime, not just the odd ones
    I don't know what you mean by this?
    zen

  7. #7
    A Banana Yoshi's Avatar
    Join Date
    Oct 2001
    Posts
    859

    Red face

    Your program will take a long long time...
    until ...
    Yoshi

  8. #8
    Registered User
    Join Date
    Nov 2001
    Posts
    241
    I had thought that it would skip the even numbers cause that would be needed to make it fast, but mine accounted for that by changing the step after 2

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Logical errors with seach function
    By Taka in forum C Programming
    Replies: 4
    Last Post: 09-18-2006, 05:20 AM
  2. Replies: 18
    Last Post: 11-04-2005, 02:41 PM
  3. prime numbers, counters, help!
    By vege^ in forum C++ Programming
    Replies: 1
    Last Post: 03-10-2003, 04:32 PM
  4. Prime numbers
    By Lazy Student in forum C Programming
    Replies: 12
    Last Post: 05-14-2002, 05:53 AM
  5. Homework help
    By Jigsaw in forum C++ Programming
    Replies: 2
    Last Post: 03-06-2002, 05:56 PM