Prime Number C++

[LatSo]

Hey c++ maniacs out there ^_^ I need your help to edit this code. In such a way that this program can generate all prime numbers from 10000-50000. BUT it will still ask the user what limit he wants but the limit should be between the said default limit ( 10k- 50k). Also, the prime number that will be generated is the prime number that every digit is also a prime number and if you combine one by one it's digit it is still a prime number. Example is 37373 , 3 is prime 37 is prime 373 is prime 37373 is prime and 37373 is also prime. Sorry for my english so if you did not understand the question well please reply and confirm. THANKS IN ADVANCE! I really need your help here guys!

int main () 
{
    for (int i=2; i<100; i++) 
    {
        bool prime=true;
        for (int j=2; j*j<=i; j++)
        {
            if (i % j == 0) 
            {
                prime=false;
                break;    
            }
        }   
        if(prime) cout << i << " ";
    }
    return 0;
}

[VernonDozier]

Example is 37373 , 3 is prime 37 is prime 373 is prime 37373 is prime and 37373 is also prime.

You have 37373 listed twice. You skip 3737, which is NOT a prime. If you're looking for an efficient algorithm, there's considerable math involved. If not, just go with a function the determines whether a number is prime and either start with a single digit number and add a digit at a time and re-check, or vice-versa.

[LatSo]

My bad listing 3737 as a prime. But to make it clear the program will only generate numbers between the said limit, and again this program will only generate prime number whose every digit is when combine one by one is also a prime.

If anyone could edit the code in my request please do so T_T

btw, is there any request section here?

[Schol-R-LEA]

Ordinarily, the best solution for primes under about 1 million would be to use the Sieve of Eratosthenes to generate all of the primes from 2 to the upper bound number. Given that the sieve requires that you start at 2, however, it may not be what your professor is looking for. Still, it is the easiest solution, and simple conditionals can then be applied to get the desired range.

I would recommend using the sieve to generate a table of primes, then go through that table with a separate test to see if a given value was a) in the desired range, and b) matched the requirement that all of the component digits are also prime.

[LatSo]

so how can you suggest to make all component digits prime? any sample codes?

[TrustyTony]

10000-50000

Start with n number primes and extend them each to n+1 number primes by prime*10+k, where k is odd. Your number will be sequence of only 1, 3, 7 and 9, naturally, except first number is 2,3,5 or 7 (1 is not prime). Even 5 and 7 are not OK for your given range wether ends are inclusive or not, as 50000 is not prime. For primality test you can use the given test made as function, but test only odd numbers 3 or more (even numbers are eliminated by the odd number at end)

[LatSo]

Can you do it? I'm kinda desperate here. My professor only teached us the basics because he don't always come to class T_T so please? :)

[TrustyTony]

You have not shown any effort yet. I have improved the algorithm in previous post, it produces the numbers in no time in my Python implementation. With C++ and given the tiny range you could even brute force check all numbers with recursive function.

[LatSo]

How can I put effort if I dont know what to do. Because in the first place my professor failed to teach us the needed knowledege to make this code because he don't come to class frequently then he gave us this project and to be pass the next meeting so I'm kinda desperate here so please if you could help me :)

[TrustyTony]

Here is good tutorial http://www.cplusplus.com/doc/tutorial/

[Lucaci Andrew]

Have a look at this code snippet: http://www.daniweb.com/software-development/cpp/code/425892/prime-numbers-in-range
But I wouldn't advise you to take it for grant, because it's a slow and unproducive algorithm.
And, beside that, i put it there just as an example to your problem. Try to figure out a better algorithm, because mine is just too ugly to present with.

[NathanOliver]

My suggestion is pretty much the same as Schol-R-LEA's. I would you a sieve of Eratosthenes to generate all number between 2 and the upper limit for your test. After that I would check and see if the number inputted is in the list. If it is then divide the number by 10 and then check again. Keep doing that until the number to check is equal to one. If you find a number that is not prime before you reach one then the number would not be prime per your conditions. You could do this with a loop but I think recursion is better suited for the task.

[TrustyTony]

My code in interpreted Python, algorithm of which I described above, but with optimized is_prime and not using the range properties, takes under 9 ms to find all existing 83 primes of the property described from one digits or longer. Little over 600 microseconds for given range in the original post of this thread, little over 1 ms for full 5 digits range without the starting number limitations.

[LatSo]

sin i replied in your post