[HELP] find closes number from array??

11/25/2012 20:19 Hikarim#1

Hi,
well i have a userinput for an integer. And i have to get sqrt of that number and find the closes number from array... and i dont rly know how to do that... can anyone help?

heres the part for my input:

Code:

int poljubnostevilo;
cin >> poljubnostevilo;
cout <<endl;
int koren = sqrt (poljubnostevilo);
cout << koren << endl;

and here's the function i use to fill in the array with prime numbers,.. etc...so this function also has to return the closest number from the array to the sqrt of the inputed integer...

Code:

int funkcijatri(int x, int n){

n = 4;
int praarray[x];
int a=0;
int sum;
    while(a<x){
              n++;
              if(IsPrime(n) && (n>=a)){
                            praarray[a] = n;
                            cout << praarray[a] << ", ";
                            sum+= praarray[a];
                            a++;

                           
              }//konec if  
            
    }//konec while
    
    
    return sum/x;
       


    
}

Hope anyone can help me :)

11/25/2012 21:16 マルコ#2

Personally I would do the following:
- Generate prime numbers by making an array of prime numbers by trying to devide each new number by every prime number. If there is always a rest, you have a new prime number. You then add it to the array
- Create a binary search tree (I think, if you fill it using the array, it will even be a Heap Tree).

Instead of an array in step 1, you should utilize the tree directly. This will speed up things pretty well.

- You now can just test if the number you are looking for is larger or smaller, then go left or right, again compare the value. If your value is in between the last and the current value tested (taken from the tree nodes), you just have to subtract the the tested numbers from the input number, use the absolute number, and then use the number with the smaller result. If the results are equal, your program has to choose one of both. You then just output it.
This way you will have quick algos for creating prime numbers and searching the closest number to the one you look for.
Please first create a list of prime numbers as this process is very very slow (especially when the numbers are getting higher. It took my friend's PC about 10h to find the first prime number with 11 digits based on CPU calculations. You could speed it up with GPU calculations by utilizing OpenCL).
You should also save this list and reload it next time to guarantee a fast startup.

Maybe this would be an overkill, but just consider how much you can learn from it ;)
You should use google and search for the methods stated above.

11/25/2012 21:41 Hikarim#3

thanks for the answer but the problem is i have to use an array in step 1,... thats the requirement... the whole program is correct according to the rules i got so far,... but i have no idea how to do this part now...

11/25/2012 22:02 マルコ#4

As I just said, you could use a tree. The performance will be great. If you have to stick to an array, why not just compare consecutive array entries.

Quote:

Originally Posted by マルコ

If your value is in between the last and the current value tested (taken from the tree nodes), you just have to subtract the the tested numbers from the input number, use the absolute number, and then use the number with the smaller result. If the results are equal, your program has to choose one of both. You then just output it.

The prime numbers are sorted, if you use my algo.