I think this is complicated problem?

[Alacaster]

I am trying to calculate primes and I know I can count on you.

My program doesn't skip any primes which makes sense due to how it works, but as it runs along it adds more and more non primes to my primes list.

Which also makes sense because it relies on the previous numbers to calculate the next but I don't know why the problem starts.

The instructions are in the code. Have fun with this mess!

Code: Select all

#include <stdio.h>
#include <stdlib.h>
#include <math.h>

#define MAX 15 // Change to calculate that many primes

/** This program calculates primes on the premise
that if a number is a multiple of a prime number
then it is not prime.

The reason why only primes are
considered is because all non prime numbers
are already multiples of a prime number and so
are included in the thesis.

For each prime 'n' found we start counting every
nth number as not prime by adding its inverse and
every time one counting variable is an integer, then
the current number we are testing is not a prime
number. And if the number is not a multiple
of any previous prime then it is prime.

 */

void primeprint(double x[MAX][2]){
    int i = 0;

    printf("\n\nPrime Numbers:\n");
    for(i = 0; i < MAX; i++){
            printf("%.0f\n", 1.0/x[i][1] );
    }

    putchar('\n');
}


void arrprint(double x[MAX][2]){

    int i = 0;

    for(i = 0; i < MAX; i++){
            printf("%f %f\n", x[i][0], x[i][1]);
    }

    putchar('\n');
}

int main(){

    int c = 2; // Number that we are checking (inadvertently)

    double primes[MAX][2]; // prime storage

    int k = 0; int i = 0; // various counters for various things

    for(i = 0; i < 2; i++){ //Set primes array to null
        for(k = 0; k < MAX; k++){
            primes[k][i] = 0.0;
        } // 'k' is not used past this point
    }

    //arrprint(primes);

    primes[0][0] = 2;   //set the first prime
    primes[0][1] = 0.5;

    i = 0; k = 0;

    while(!primes[MAX-1][0]){ //main body

        //printf("\n%d\n", c);
        //arrprint(primes);

        while(primes[i][0]){ //check if there are any integers in the primes list
            if( !(primes[i][0] - (int)primes[i][0]) ){
                goto SET; //If there are then 'c' is not prime
            }
            //printf("%d\n",i);
            ++i;
        }

        primes[i][0] = c;
        primes[i][1] = 1.0/((double)c);

        printf("Prime Set\\> \n%2d %f\n", c, primes[i][0]);


        SET:
        c++;
        i = 0;
        while(primes[i][0]){
            primes[i][0] += primes[i][1]; //The primes are actually stored as inverses in primes[foo][1]
            ++i;
        }
        i = 0;
        k = 0;

        printf("\n%d\n", c);
        arrprint(primes);

    }

    i = 0;

    primeprint(primes);
    printf("\n%d", c);

    return 0;

}

[Alacaster]

Too complicated?

[chili]

Too C for me :kappa:

[Alacaster]

Hey, I figured it out. My theory was wrong. I don't know if anyone has ever calculated primes like this before.

I have a list of primes and a counter for each prime. The counters get incremented and everytime they increment a prime number of times the counting variable is a multiple of a prime which is not a prime number. Then it gets reset to zero.

Code: Select all

#include <stdio.h>
#include <stdlib.h>

#define MAX 500

void arrprint(int x[MAX][2]){

    printf("Primes:\n");
    int i = 0;
    while(i < MAX){
        printf("%8d\n", x[i][0]);
        i++;
        }

}

int main()
{
    int primes[MAX][2]; //primes and prime counters

    for(int b = 0; b < MAX; b++){ //Nullify primes
        for(int k = 0; k < 2; k++){
            primes[b][k] = 0;
        }
    }

    primes[0][0] = 2; //Set first prime
    primes[0][1] = 1;

    int k = 1; int b = 0;

    int c = 3;
    int n = 0;

    while(!primes[MAX-1][0]){
        //arrprint(primes); // Uncomment to understand
        while(n < k){
            if(primes[n][1] == primes[n][0]){
                goto SET; //if c is a multiple of any prime then go to SET
                }
            n++;
        }

            primes[k][0] = c;
            primes[k++][1] = 0; //Set prime
            b = 1;

    SET:

        for(n = 0; n < k; n++){
            if(primes[n][1] == primes[n][0]){ //Set primes that c is a multiple of to zero
                primes[n][1] = 0;
            }
        }

        for(n = 0; n < k; n++)
            primes[n][1]++;

        c++;
        n = 0;
        b = 0;
    }

    arrprint(primes);

    return 0;
}

[Alacaster]

Everytime I look away I forget my theory behind it. There was a lot of debugging and if you change anything it won't work so don't try. I don't even remember how it works exactly.

[Alacaster]

I calculated 50,000 primes in 2.4 minutes. Is that good? I'm on a trash laptop.

[Alacaster]

If you want to know how much longer it takes to calculate more primes then check out this graph. https://www.desmos.com/calculator/ik6xnibx0p

[chili]

Desmos is a nice site.

If you wanna get speed, need to MT and SIMD that biotch

[Yumtard]

How about this?

Code: Select all

#include <iostream>

int main()
{
	const int max_primes = 500;
	int primes[max_primes];
	bool is_prime;
	int count = 0, n = 1;

	while (count < max_primes)
	{
		n++;
		is_prime = true;

		for (int i = 0; i < count && is_prime; i++)
			if (n % primes[i] == 0)
				is_prime = false;

		if (is_prime)
			primes[count++] = n;
	}

	for (int j = 0; j < max_primes; j++)
		std::cout << primes[j] << std::endl;

	return 0;
}

35 seconds to calculate and print out 100 000 primes for me

[Alacaster]

How about this?

Yeah, but that's the normal way. Mine is faster for x or less primes though. I think, I don't know how modulus works.

I'm going to try my method on my fast desktop later.