Finding Correct Numbers Combination

[jgg2002]

John wants to unlock an electrical lock and needs a password to gain access. He is given a set of N numbers and some of these numbers generate the password. The numbers that are selected have equal distance to 2 prime numbers. Also, the password consists of unique numbers, there can't be two 6s for example in the final answer.

Example:
10
12 3 100 5 21 9 8 7 6 4
Password:
100
21
9

So I thought of handling this with creating an array that has the positions of all the prime numbers, and then, if the distance between two positions is not even, divide it by two and then input the initial array's (all the numbers) matching the distance/2 pushed in the front of a list. The use unique() on the lists and just output it.

Here's my code:

  #include<iostream>
#include<list>
using namespace std;
bool compare_sort (const int& first, const int& second) //used to sort a list
{
    if (first>second) return true;
    else if (first<second) return false;

}
bool prime(int a){       //function for checking if a number is prime or not
    bool primebool=true;
    if(a==1){
        primebool=false;
    }
    else{
        int half=a/2;
        for(int i=2; i<=half; i++){
            if(a%i==0){
                primebool=false;
                break;
            }
        }
    }
    return primebool;
}

int main(){
int m; //total number of integers
cin>>m;

int arr[m];  
int check;
int primes=0;
for(int i=0;i<m;i++){
    cin>>arr[i];  //initial number group
    check = arr[i];
    if(prime(check)){
        primes++;   //finds the number of primes
    }
}

int pos[primes];  //declaring the positions array
int counter=0;  //will be used to input all the positions
for(int i=0;i<m;i++){ //finds all positions of prime numbers
    int k=arr[i];
    if(prime(k)==true){ 
        pos[counter]=i;
        counter++;
    }
}

list<int> password(primes); //declaring the list with a size of primes, just in case
int help;
for(int i=0; i<(counter-1); i++){  
    for(int j=i+1; j<counter; j++){
        int distance=pos[j]-pos[i]-1; \\-1 array begins at 0
        if(distance%2==1){
            int place=(distance/2)+1;
            help=arr[pos[i]+place];    //finds a number that is in the answer
            password.push_front(help);
        }
    }
}
password.sort(compare_sort) //here I sort.
password.unique(); //speaks for itself I guess

for(list<int>::iterator it = password.begin(); it!=password.end(); it++){
    cout<<*it<<endl;
}

return 0;
}

The code works but only in a few test cases.

[ne555]

> The numbers that are selected have equal distance to 2 prime numbers.
sorry, don't understand, ¿may you rephrase?


> The code works but only in a few test cases.
¿by instance?

[jgg2002]

¿may you rephrase?

For example in the row 1 13 4 12 9 7 3 5 the number 12 would be on of the selected numbers because it's distance from 13 (2) is equal to the distance from 7 (2). Both 13 and 7 are prime numbers.

he code works but only in a few test cases. ¿by instance?

In the following it doesn't, and I think there are more:
10
2 3 5 7 9 11 13 17 23 29
The normal output should've been all the numbers except 2 and 29, but it outputs this:

23
19
17
13
17
13
11
13
11
7
13
11
7
5
11
7
5
3

[jgg2002]

And it's strange that it has repeating numbers, since I used unique()

[cire]

And it's strange that it has repeating numbers, since I used unique()

Have you considered that since unique removes consecutive duplicate elements, it might make sense to sort the list first?

[jgg2002]

@cire.
Totally forgot about that.... But even if I do the answer would still be wrong because the autocompiler's test cases' answers are by the order that they are found so it gives me 0/100...

[jgg2002]

Actually it gave me 40. So I guess I'm stuck. I am not really sure it's because I sorted it or because there is something wrong with my algorithm...

[cire]

I can't actually use your code as posted since it isn't legal C++ and I don't currently have a compiler installed with the gcc vla extension, but if I replace your vlas with a vector I get a noticeable difference in output from what you were reporting.

Here's what I would do, assuming I'm understanding the requirements correctly:

Read the input into a container, c. Store the prime indexes in order in another container, p.

Loop through all elements in c that are higher than p.front() and lower than p.back(), and for every element iterated over determine if there is a pair of indexes in p which satisfy the equidistant requirement for the index of the current element. If so, add it to a third container, r.

The contents of r should be the password.

[jgg2002]

I can't actually use your code as posted since it isn't legal C++

What do you mean by that?

[cire]

What do you mean by that?

In C++ the size of arrays must be a compile-time constant. In your code, you have two arrays that violate this requirement.

[jgg2002]

The size of the array is a variable that has a value. For example, int arr[m]; will have a certain value while the program runs, since the code:
int m; cin>>m; is before the declaration of the array. I didn't declare the array before knowing the size. In my compiler (Code::Blocks) this code runs without error.

[cire]

In my compiler (Code::Blocks) this code runs without error.

That's because you have a non-standard extension enabled. That doesn't make it legal C++.

[jgg2002]

Finally found the answer

#include<iostream>
#include<list>
using namespace std;
bool password[1000];
bool prime(int a){
    bool primebool=true;
    if(a==1){
        primebool=false;
    }
    else{
        int half=a/2;
        for(int i=2; i<=half; i++){
            if(a%i==0){
                primebool=false;
                break;
            }
        }
    }
    return primebool;
}

int main(){
int m;
cin>>m;

int arr[m];
int check;
int primes=0;
for(int i=0;i<m;i++){
    cin>>arr[i];
    check = arr[i];
    if(prime(check)){
        primes++;
    }
}

int pos[primes];
int counter=0;
for(int i=0;i<m;i++){
    int k=arr[i];
    if(prime(k)==true){
        pos[counter]=i;
        counter++;
    }
}


int help=0;
for(int i=0; i<(counter-1); i++){
    for(int j=i+1; j<counter; j++){
        int distance=pos[j]-pos[i]-1;
        if(distance%2==1){
            int place=(distance/2)+1;
            password[pos[i]+place]=true;
            help ++;
        }
    }
}
for (int j=0; j<m; j++){
    if (password[j]==true){
        cout<<arr[j]<<endl;
    }
}

return 0;
}

Thx for the help