Programming Forums > Projects > Show Off Your Open Source Projects

rsnd · Sep 11th, 2006, 4:38 AM

Nice! I remember doing something like this in pascal....finding the 10000th prime...took ages to calculate.

MBirchmeier · Sep 11th, 2006, 9:04 AM

Quote:

Originally Posted by titaniumdecoy

 cpp Syntax (Toggle Plain Text) 
bool is_prime(int x) {
    if (x % 2 == 0 || x == 1)
        return false;
    for (int i = 3; i <= sqrt(x); i += 2)
        if (x % i == 0)
            return false;
    return true;
}
bool is_prime(int x) {
    if (x % 2 == 0 || x == 1)
        return false;
    for (int i = 3; i <= sqrt(x); i += 2)
        if (x % i == 0)
            return false;
    return true;
}

The only suggestions I have with this code (and Kaja's) is the compare statement.

with titaniums having a sqrt in the loop is slower. (IIRC sqrt is 63 clock cycles, the same as modulo) this almost doubles the execution time of this block. A good optimizer might break out this statement, but

(Toggle Plain Text)

int root = sqrt(x);
for (int i = 3; i <= root; i += 2)

will be no worse, and probablly better depending on the optimization level.

With Kaja's it's only a muliplication (1 clock cycle IIRC) but it still gets executed each time around, so it's faster for numbers < 170,000 (but slower for numbers divisible by nothing smaller than 139).

Since you're not calculating 2^(2^very_large_prime) it doesn't matter too much, but I still figure'd I'd chime in.

-MBirchmeier

peaceofpi · Nov 1st, 2006, 9:44 PM

Little late, but I think this one works. Got it all on my own in about a half hour. Not commented cause I didn't get lost and probably would if I commented. It's pretty simple anyway

(Toggle Plain Text)

#include <iostream>
#include <cstdlib>

int n = 1;
int count = 1;

void prime(int x)
{

	std::cout << x << "'s factors: ";
	for (; n <= x/2; n++)
	{
		if (x%n==0)
		{
			std::cout << n << " ";
			if (n > 1)
				count++;
		}

	}
	if (count >= 2)
		std::cout << std::endl << x << " is not prime";
	else
		std::cout << std::endl << x << " is prime";
}

int main()
{
	int x;
	std::cout << "Enter number: ";
	std::cin >> x;
	prime(x);
	std::cout << std::endl;
	system("pause");
}

andro · Nov 2nd, 2006, 1:02 AM

Wrote this about a year ago, dug it up when I saw this...

(Toggle Plain Text)

#include <stdio.h>
#include <math.h>
#include <stdlib.h>
#include <sys/time.h>
#include <time.h>

void sieve(int n, int *primes);

int main(int argc, const char **argv)
{
    if (argc < 2)
		return -1;

    int n = atoi(argv[1]);
    int *primes = calloc(n, sizeof(int));
    int numprimes = 0;
    
    struct timeval timea, timeb;
    
    for (int i = 2; i < n; i++) 
    {
        *(primes+i) = 1;
    }
    
    gettimeofday(&timea, NULL);
    sieve(n, primes);
    gettimeofday(&timeb, NULL);
    
    
    for (int i = 0; i < n; i++) 
    {
        if (*(primes+i))
        {
            numprimes++;
        }
    }
    
    int delta_s     = timeb.tv_sec  - timea.tv_sec;
    int delta_us    = timeb.tv_usec - timea.tv_usec;

    float delta     = delta_s + delta_us / 1000000.0;
    
    printf("Took %f millseconds.\n", delta*1000);
    printf("Found %d primes.\n", numprimes);
    
    return 0;
}

void sieve(int n, int *primes)
{
    int max = floor(sqrt(n));

    for (int i = 2; i <= max; i++)
    {

        if (*(primes+i))
        {
            for (int j=i*i; j <= n; j+=i)
            {
                *(primes+j) = 0;
            }
        }
    }

}

(Toggle Plain Text)

mbp:~/Desktop andro$ ./sieve 10000000 
Took 528.309998 millseconds.
Found 664579 primes.

Sep 11th, 2006, 4:38 AM	#21
rsnd Hobbyist Programmer Join Date: Jun 2005 Location: Helltown Posts: 162 Rep Power: 4	Nice! I remember doing something like this in pascal....finding the 10000th prime...took ages to calculate. __________________ Spread your wings and fly! Chicken!

Nov 1st, 2006, 9:44 PM	#23
peaceofpi hi: for(;;) goto hi; Join Date: Jun 2006 Posts: 87 Rep Power: 3	Little late, but I think this one works. Got it all on my own in about a half hour. Not commented cause I didn't get lost and probably would if I commented. It's pretty simple anyway (Toggle Plain Text) #include <iostream> #include <cstdlib> int n = 1; int count = 1; void prime(int x) { std::cout << x << "'s factors: "; for (; n <= x/2; n++) { if (x%n==0) { std::cout << n << " "; if (n > 1) count++; } } if (count >= 2) std::cout << std::endl << x << " is not prime"; else std::cout << std::endl << x << " is prime"; } int main() { int x; std::cout << "Enter number: "; std::cin >> x; prime(x); std::cout << std::endl; system("pause"); } #include <iostream> #include <cstdlib> int n = 1; int count = 1; void prime(int x) { std::cout << x << "'s factors: "; for (; n <= x/2; n++) { if (x%n==0) { std::cout << n << " "; if (n > 1) count++; } } if (count >= 2) std::cout << std::endl << x << " is not prime"; else std::cout << std::endl << x << " is prime"; } int main() { int x; std::cout << "Enter number: "; std::cin >> x; prime(x); std::cout << std::endl; system("pause"); } __________________ How do you play Religious Roulette? Stand around in a circle and blaspheme till someone gets struck by lightning.

Nov 2nd, 2006, 1:02 AM	#24
andro Professional Programmer Join Date: Oct 2005 Location: California Posts: 294 Rep Power: 3	Wrote this about a year ago, dug it up when I saw this... (Toggle Plain Text) #include <stdio.h> #include <math.h> #include <stdlib.h> #include <sys/time.h> #include <time.h> void sieve(int n, int primes); int main(int argc, const char argv) { if (argc < 2) return -1; int n = atoi(argv[1]); int primes = calloc(n, sizeof(int)); int numprimes = 0; struct timeval timea, timeb; for (int i = 2; i < n; i++) { (primes+i) = 1; } gettimeofday(&timea, NULL); sieve(n, primes); gettimeofday(&timeb, NULL); for (int i = 0; i < n; i++) { if ((primes+i)) { numprimes++; } } int delta_s = timeb.tv_sec - timea.tv_sec; int delta_us = timeb.tv_usec - timea.tv_usec; float delta = delta_s + delta_us / 1000000.0; printf("Took %f millseconds.\n", delta1000); printf("Found %d primes.\n", numprimes); return 0; } void sieve(int n, int primes) { int max = floor(sqrt(n)); for (int i = 2; i <= max; i++) { if ((primes+i)) { for (int j=ii; j <= n; j+=i) { (primes+j) = 0; } } } } #include <stdio.h> #include <math.h> #include <stdlib.h> #include <sys/time.h> #include <time.h> void sieve(int n, int primes); int main(int argc, const char *argv) { if (argc < 2) return -1; int n = atoi(argv[1]); int primes = calloc(n, sizeof(int)); int numprimes = 0; struct timeval timea, timeb; for (int i = 2; i < n; i++) { (primes+i) = 1; } gettimeofday(&timea, NULL); sieve(n, primes); gettimeofday(&timeb, NULL); for (int i = 0; i < n; i++) { if ((primes+i)) { numprimes++; } } int delta_s = timeb.tv_sec - timea.tv_sec; int delta_us = timeb.tv_usec - timea.tv_usec; float delta = delta_s + delta_us / 1000000.0; printf("Took %f millseconds.\n", delta1000); printf("Found %d primes.\n", numprimes); return 0; } void sieve(int n, int primes) { int max = floor(sqrt(n)); for (int i = 2; i <= max; i++) { if ((primes+i)) { for (int j=ii; j <= n; j+=i) { *(primes+j) = 0; } } } } (Toggle Plain Text) mbp:~/Desktop andro$ ./sieve 10000000 Took 528.309998 millseconds. Found 664579 primes. mbp:~/Desktop andro$ ./sieve 10000000 Took 528.309998 millseconds. Found 664579 primes.

Thread Tools
Show Printable Version Email this Page
Display Modes
Linear Mode Switch to Hybrid Mode Switch to Threaded Mode

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
Median/Mode in arrays? {Need help}	Java\|Tera	Java	27	Nov 29th, 2005 10:50 AM
Prime Numbers	Konnor	C++	6	Sep 12th, 2005 6:46 PM
Generating prime and composite numbers	saadmir	C	5	Sep 9th, 2005 4:08 PM
Prime numbers	thomzor	C++	24	May 20th, 2005 2:02 PM
Help with a couple prime numbers programs!!	BehemothPhoenix	C++	3	Mar 20th, 2005 2:06 PM

Currently Active Users Viewing This Thread: 1 (0 members and 1 guests)

Programming Forums > Projects > Show Off Your Open Source Projects

Calculate prime numbers