Project Euler # 41

[chillen0707]

We shall say that an n-digit number is pandigital if it makes use of all the digits 1 to n exactly once. For example, 2143 is a 4-digit pandigital and is also prime.

What is the largest n-digit pandigital prime that exists?

^Question Above ^


This program works when I set max to any number < one million.
Problem is I need to set it to 987,654,321. I'm using bloodshed Dev compiler.
I thought that INT can hold up to 2,147,483,647. Welcome help, tips, etc;

 
#include <iostream>
#include <algorithm>
#include <vector>
#include <sstream>
#include <string>
using namespace std;

int main(){
    
    string  f="000000000", g="00000000", h="0000000", j="000000", k="00000", l="0000";
    int max = 1000000000;
    vector<int> myvector;
    bool list[max];
    
    for(int x = 0; x < max; x++){
            list[x] = true;}
    
    list[0] = false;
    list[1] = false;
    
    for(int x = 0; x < max; x++){
            if(list[x] == true){
                       myvector.push_back (x);
                                           for(int y = x + x; y < max; y+=x){
                                                   list[y] = false;}}}
                                           
    reverse(myvector.begin(),myvector.end());  
    
    for(int x = 0; x < myvector.size(); x++){
           
            int a = myvector[x];
            int c = 0;
            
            stringstream num;
            num << a;
            string number = num.str();
           
            for(int y = 1; y <= number.length(); y++){
           
                   int b = y;
                   
                   stringstream num_two;
                   num_two << b;
                   string checker = num_two.str();

                   for(int z = 0; z < number.length(); z++){
                           if(number[z] == checker[0]){
                                        number[z] = '0';
                                        c++;
                                        break;}}}
                                        
        if(((number == f) || (number == g) || (number == h) || (number == j) ||(number==k)||(number==l)) && (c == number.length())){
                             cout<< myvector[x]<<endl;}
                    }
            
            system ("Pause");
            return 0;}

[chillen0707]

sorry to bump but would really like solution

[norm b]

Stack size is your problem. There's not enough space for one billion bools.

Allocate your array "list" on the heap: bool *list = new bool[max];

And be sure to call delete [].

[giblit]

I can tell you the largest possible would be 7 if you do a few simple analysis.

Think about it: 9 + 8 + 7 + 6 + 5 + 4 + 3 + 2 + 1 = 45 which is divisible by 3
8+7+6+5+4+3+2+1 = 36 which is divisible by 3
7+6+5+4+3+2+1 = 28 which is good
6+... = 21 which is divisible by 3
5+.. = 15 which is divisible by 3
4+.. = 10 which is good

so this means we are probably looking 7 digit number.

The possible choices would then be:
7654321
7564321
7546321
...
1234567

we can even then remove a few things like the last digit can't be a 2,4,5, or 6.

You can also make a sieve pretty easy for the 8 million numbers. Though you would actually only need to sieve to the sqrt of 7654321 ~ 809

So this means you need a sieve of 809 numbers which is really easy to do with your memory.

*edit PS a few helpful things to use are a std::vector<bool> for the sieve and using std::next_permutation for getting the permutations of 7654321. Then all you have to do is check if they are prime. There are 5040 possible choices. With brute force that would leave a maximum number of iterations of 4077360. Though many numbers will only use a few iterations before they are found as composite


*edit 2 if you want to know how I solved it here is what I did.
1) a while back I created a very large text file that contains the primes up to 4.5 billion.
2) I read in the numbers(prime from file) from 2314->4321 and 1234567->7654321 then I simply checked if they were a permutation of 1234 or 1234567 (depending on the number read in) which took me only a few milliseconds to find the answer.