Primes rage

[otakujome]

Hello dear readers, this is my first time posting on this forum. I haven't been learning C++ for a long time, so I decided to train with practice tasks including algorithms. The problem that I have is that my algorithm is too slow for the thing that I want, I used the quite basic prime algorithm. Also I used vector library. I optimized the code quite a lot in the last hour or so, but for some reason output doesn't work, and I as the standard quite newbie have no idea what to do, because it 'sometimes' outputs and sometimes doesn't, it makes absolutely no sense to me. Also I'm working on a 10 year old nearly dead computer...

Btw, I'm 14 years old.

This is the code

#include <iostream>
#include <cmath>

using namespace std;

    bool IsPrime(int number)
    {
        if (number < 2) return false;
        if (number % 2 == 0) return (number == 2);
        int root = (int)sqrt((double)number);
        for (int i = 3; i <= root; i += 2)
        {
            if (number % i == 0) return false;
        }
        return true;
    }

int main () {
    int primeArrayCount, primeUp, primeDown, current, successCounter, output, outputValue;
    cin >> primeArrayCount;
    int primeArray [primeArrayCount][10000];
    for (int n=0;n<primeArrayCount;n++) {
        cin >> primeDown >> primeUp;
        primeArray[n][0] = primeDown;
        primeArray[n][1] = primeUp;
        primeArray[n][2] = 0;
    }
    for (int n=0;n<primeArrayCount;n++) {
        for (int x=0;x<((primeArray[n][1])-(primeArray[n][1]));x++) {
            current = ((primeArray[n][0])+x);
            if (IsPrime(current)) {
               (primeArray[n][3+(primeArray[n][2])]) = current;
               (primeArray[n][2])++;
               }
        }
    }
    for (int n=0;n<primeArrayCount;n++) {
        successCounter = (primeArray[n][2]);
        for (int x=0;x<successCounter;x++) {
            outputValue = 3+x;
                int output = (primeArray[n][outputValue]);
                cout << output << endl;
            }
        cout << endl;
    }
    system("pause");
    return 0;
}

[kbw]

It's not clear what your algorithm is or why it needs 10000 of everything or why you need a floating point operation, ... or any of it.

Perhaps if you explained in words what you're trying to encode, it'll all be clear.

[otakujome]

I am trying to make faster algorithm, I put 10000 spaces in array because I am testing with big numbers. Basic thing I'm trying to do here is a faster prime finder.

The input:

Number of test cases for primes(int)
TestCase1Lower number and upper number (int int)
All other test cases in same format


Then it's supposed to go through all pairs of numbers and export them into suiting arrays, I made a working one before, but the problem is that it wasn't fast enough. I think problen is conversion between float and int. But I can't find a faster way. Main thing I need is a fast prime algorithm, and a fast way of conversion to int (rounding the square root of number and then equalizing an integer variable with it?)

The end is just printing it out, but the code acts wierd. I think it might be that the for loop has one value as integer and othwr as something else and is lost. I'm not good at debugging and finding mistakes. Basically, if I try to even print output of anything, there are no values stored under the cells in array, which means it doesn't print, which brought me to thinking it's an error in for loop, but it still won't print outside of it. I'm lost.

[TheIdeasMan]

Hi,

Can we ask you to edit your original post, select al the code, then press the <> button, so it uses code tags?

Your code should look like this:

#include <iostream>
#include <cmath>

using namespace std;

bool IsPrime(int number)

I took a different approach to this problem:

I put 2, into a std::list, then all the odd numbers from 3 to 2,000,001. LIMIT = 2000000

then I remove all multiples of 3.

The next number in the list is 5, so I remove all multiples of it.

And so on, for each next number in the list, until sqrt(LIMIT)

The good thing about this algorithm is that the amount of remaining numbers reduces quickly.

I got this to work up to 2 million in less than 1 second. Remember it's finding all the primes.

Once you have the list, it is quick to see if a specific number is in the list.

However there are some inefficiencies. Say we are checking for multiples of some prime around 1001, we shouldn't need to check every number that remains in the list. But multiples of 1001 might have already been removed from the list. Edit in fact all the multiples of all the numbers less than 1001 are already gone. so we only need to start from 1001².

I am not sure whether another container might be better, std::unordered_list maybe ? Not sure how good that is when it has to access every item.

std::vector is no good IMO, even with move semantics, if 1 item is removed then all the others have to be moved along 1. Might be wrong about that though.

Hope this helps :+)

[otakujome]

Thank you for help with formatting on forums.

I am thinkinh of different approaches, my first one was the most basic one, the first one people normally learn, but it seems to be too slow for what I need, so my main 2 things are that I need to test a number to see if it's prime, and if it is I store it into array as integer. And the rest is simple, printing out and such.

This is original, too slow, code.

#include <iostream>
#include <vector>

using namespace std;

int main () {
	int testCount;
	int input1;
	int input2;
	bool isPrime;
	vector<int> rangeDown;
	vector<int> rangeUp;
	cin >> testCount;
	for (int i = 0;i<testCount;i++) {
		cin >> input1 >> input2;
		rangeDown.push_back(input1);
		rangeUp.push_back(input2);
		}
	vector<vector<int> > primes(testCount);
	for (int j = 3;j<testCount;j+=2) {
		for (int first = rangeDown[j]; first<=rangeUp[j]; first++) {
			for (int second = 2; second<=first; second++) {
				if ((first%second) == 0) {
					if (first==second) {
						isPrime=true;
						} else {
                               isPrime=false;
                               break;
                               }
					}
				}
			if(isPrime) {
                        primes[j].push_back(first);
                        }
			}
		}
	for (int x = 0;x<primes.size();x++) {
		for (int y = 0;y<primes[x].size();y++) {
			cout << primes[0][y] << endl;
			}
		cout << endl;
		}
}

[kbw]

Interesting algorithm. Ever heard of Sieve of Eratosthenes?
https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes

[TheIdeasMan]

Hi,

otakujome wrote:

...... are that I need to test a number to see if it's prime ......

That's where the inefficiency come from, because all the numbers up to n are tested, then all the numbers up to n+1 are tested again. This results in O(n!) which is very bad, and would only be practical for very small numbers.

This is an example where the wrong algorithm can take a computer 1000 years to work out (literally), but a good algorithm can take less than 1 second to do the same thing.

As kbw says Sieve_of_Eratosthenes is the way to go, but don't apply it in a function to n, n+1, n+2 ... Otherwise you will have the same problem still. Use it to operate on the whole list.

Which is what the algorithm I mentioned above does :+) Although Euler's sieve (on the same wiki page) is better because it doesn't test every number in the list.

Good Luck :+D