Primes < n

[Growl]

Hey!

There are two main problems with this program:
* Program counts 1 and 0 as a prime
* I didn't get where to write this form 2^k -1 in the program code..

I would be much happier if there is a way to change second program a little bit and it would cout a whole list of prime numbers, not just one of them. Is there a easiest way to do that?

There is an integer n.
Find primes that is < than n (p < n) and they can be expressed in the form 2^k-1.

VERSION 1

#include <iostream>
#include <math.h>
using namespace std;

void p(int);
int main()
{
    cout << "INT n! " << endl;
    cout << endl;
    int n;
    cin >> n;
    cout << endl;
    cout << endl;
    p(n);
}
void p(int n)
{
    bool IR = true;
    for(int i = 0; i <= n; i++)
    {
        for(int j = 2; j <= n; j++)
        {
            if ( i!=j && i % j == 0 )
            {
                IR=false;
                break;
            }
        }
        if (IR)
{
cout << i << endl;
}
IR = true;
}
}

VERSION 2

#include <iostream>
#include <math.h>
using namespace std;

int p(int n)
{
    if (n < 2)
    return 0;
if (n > 2 && (n % 2) == 0)
return 0;


return 1; //

int main()
{
    int n;

        cout << "cin n: ";
        cin >> n;
        if (n)
        {
            if (p(n))
            cout << n << "is!" << endl;
            else
            cout << n << "is not!" << endl;
            }
            }

[Chervil]

Well, the second program doesn't compile (there's a closing brace missing from function p. And it doesn't work, it just checks whether the number is odd, after correctly handling 1, 2 and 3.

I'd recommend using the first program as your basis for further development.

Still, you've made no attempt here to address "numbers which can be expressed in the form 2^k-1".

Here's a crude attempt at that part:

#include <iostream>

    using namespace std;

int main()
{
    // Generate integers of the form 2^k-1  
    for (int k=0; k<32; ++k)
    {
        int n = 1;                  // find 2 ^ k

        for (int i=0; i<k; i++)
        {
            n = n * 2;
        }

        n = n - 1;                  // subtract one

        cout << n << endl;
    }

    return 0;
}

I'd suggest you re-write the question. This is the original:

There is an integer n.
Find primes that is < than n (p < n) and they can be expressed in the form 2^k-1.

Reword it like this:

There is an integer n.
Find numbers that 
    can be expressed in the form 2^k-1
    and are less than n
    and are prime.

[Growl]

Thanks a lot!
Now I'm going to finish this program (finally)... :)
(which I try for about 2 weeks and still no good results.. :D)

[Growl]

Almost done! Just a few things....

Program looks like this:

#include <iostream>
#include <math.h>
using namespace std;

int main()

{
  int OKZ;
  int n = 0;
do
{
    cout << "INPUT n: " << endl;
    cin >> n; cout << endl;
    for (int k=0; k<n; ++k) // Part of program that generates integers of the form 2^k-1  
    {
int n=1; // subtract one
for (int i=0; i<k; i++)
    {
    n=n*2;
    }
    n=n-1; // subtract one
    }
    bool OK = true;
    for(int i = 0; i <= n; i++)
    {
        for(int j = 2; j <= n; j++)
        {
            if (i!=j && i % j == 0 )
                {
                OK=false;
                break;
                }
        }
        if (OK)
        {
            cout << i << endl;
        }
        OK = true;
    }
cout << " continue (1) or end program (0)?" << endl;
cin >> OKZ; //
    }
while (OKZ == 1);
return 0;
}

IF n=12
PROGRAM PRINTS:
1
2
3
5
7
11

IF n=7
PROGRAM PRINTS:
1
2
3
5
7

IF n= -1 [ IF cin numbers in interval (-∞; 0] ]
PROGRAM PRINTS:
" " [empty space]

Ja n=1
PROGRAM PRINTS:
0
1

So 1 is prime? I know that 0 isn't but it count if I cin 1, so something is not right... :(
Please help last time!

[Chervil]

Almost done?

What about the first part of the program (the 2^n-1 section). What kind of output are you producing from that?

And as for the second part of the program, it just produces a list of every prime number less than n. Don't you thing there ought to be some sort of relationship between parts one and two?

As for 1 being a prime number, how about this. Notice lines 3 and 4.
Instead of having all of your code inline, it might be simpler to just call this to see whether or not the value is a prime number.

bool isprime(unsigned int n)
{
    if (n<2)
        return false;

    for (unsigned int j = 2; j < n; j++)
    {
        if (n % j == 0 )
            return false;
    }
    return true;
}

Though as I said several days ago, there's no need to check for division by values greater than the square root of the number. That improves the efficiency considerably. Bear in mind that when using 2^n-1, you very quickly find the numbers you are dealing with are very large.

[Growl]

Thats the problem... I do not understand how to combinate those two programs together... How to make this relationship :/
Ehh.. my problem..

[Chervil]

Just throw away part two, you don't need it. Keep part one. Print out the numbers it generates. But you need to add two tests before printing.

If the number generated is bigger than the original input limit n, you can exit the loop and finish.

if (x > n)
    break;

And secondly, just need to add an if condition, and test that the number is prime or not. If it isn't prime, then you don't need to print it.

That's why I suggested using a separate function to test whether the number is prime or not. It keeps that complicated stuff out of the way, in its own separate place. Just call the function and test the result.

if (isprime(x))
    cout << x << endl;

Frankly, I don't think I could be much clearer without actually writing the complete code for you. And to be honest I've already contributed some pretty big chunks of what you need. All you need to do is to fit together the various pieces.

I'm not sure whether your difficulty here is in the C++ code, or simply that you don't really understand the original question.

[Chervil]

You can check your results against the list here:
http://en.wikipedia.org/wiki/Mersenne_prime#List_of_known_Mersenne_primes

and if you want to understand the topic more thoroughly, then google "Mersenne Prime"

[Growl]

I understand the mathematics and things what to do...
Without part two it is a lot more worst... Program doesn't work like it should at all anyway...
BTW There is no need for arrays?

Can you believe that in PASCAL I always get more than 85% (mark) in programming?

Ehh... I'm pretty sure that you think that I'm f***ing retarded, but I can't just get this program done with C++ and Saturday is last day to show this "program" to professor. I have no chances to get 40% because I need for about 20h of studying in order to understand C++ programming language (in my opinion it is not similar programming language at all) :/

Thank you anyway! Im very grateful for your help!

[Chervil]

To be fair, you need some of part two. That is, you need the part where it tests the number to determine whether or not it is prime.

But the outer part, namely this, is not relevant:

    for (int i = 0; i <= n; i++)
    {
       // body of part two here
    }

What you need to do is to grab the important stuff from part 2, put it into part 1, and when you've done that, all that will remain of part two will be the empty shell, much like I posted here.

Actually, I'm willing to help, but I think there's something not right. It feels like I'm missing something here.

Maybe you could write the program in Pascal and then use that in effect as pseudocode to steer your C++ implementation?

Perhaps it would be better if someone else joined this thread and gave a different point of view. Anyone?

[Growl]

A friend recommended to use this:

    for(int k = 0; k < (int)pow((double)2,k) - 1; k++
    {
    // check if (int)pow((double)2,k) - 1 is prime
    }

Looks difficult :/

[Chervil]

Actually, the above suggestion is not quite right.

Try this and see, there is no output:

    for (int k = 0; k < (int)pow((double)2,k) - 1; k++)
    {
        cout << "k = " << k << endl;
    }

But still, it has some of the right ingredients.
Re-arrange it like this, and you might be on to something.

    for (int k = 0; k < 32; k++)
    {
        int m = (int)pow((double)2,k) - 1;
        // check if m is prime
        cout << "k = " << k << "  m = " << m <<  endl;
    } 

In fact the values output from the above are the same as that from the code I posted six days ago:

    // Generate integers of the form 2^k-1
    for (int k=0; k<32; ++k)
    {
        int n = 1;                  // find 2 ^ k

        for (int i=0; i<k; i++)
        {
            n = n * 2;
        }

        n = n - 1;                  // subtract one

        cout << "n = " << n << endl;
    }

All you need to do is to test whether the number is prime before outputting it. And in addition, a very simple check, make sure that it is less than some limit specified by input from the user.

If you're not sure how to check whether the number is prime, please see the isprime() function which I posted a few days ago.

I don't know any more. There's a saying, you can lead a horse to water, but you can't make it drink. All the answers are right there in front of your eyes. Just open them for a brief moment and look. Please. This is driving me crazy.

I also offer my apologies for seemingly having poisoned this thread, since no-one else seems willing to dip their toe in the water and join in.

[Growl]

THANKS A LOT! :)



I'm done with connecting parts together - all works fine! But I need to replace (pow(2,p)-1) because my professor has forbidden pow...

BTW what does

m

means?
Actually I don't really understand this part (that works (can somebody explain what does this part do?)):

Misunderstooded part

#include <iostream>
#include <math.h>
using namespace std;

int IsPrime(unsigned long m)

{
    for(unsigned long p=2;p<m/2;p++)
{
    if(m%p==0)
    return 0;
}
return 1;
}

n - integer
p - prime number (if cout << p it prints list of primes
m - [???]

#include <iostream>
#include <math.h>
using namespace std;

int IsPrime(unsigned long m)

{
    for(unsigned long p=2;p<m/2;p++)
{
    if(m%p==0)
    return 0;
}
return 1;
}

int main()
{
                    int oky;
                    do{
        int n=0;
        cout << endl << "<<<<< Input integer n: >>>>> " << endl;
        cin >> n;

    for(unsigned long p=2;p<20;p++)
    {
        if (((pow(2,p)-1)<n) && IsPrime(pow(2,p)-1))
        cout<<endl<<pow(2,p)-1;
    }

                    cout << endl << endl << " continue (1) end (0)?" << endl;
                    cin >> oky;}
                    while (oky == 1);
return 0;
}

BTW program do not work as before If I replace

pow

with this

    for(unsigned long p=2;p<20;p++)
    {
        if ((((2^p)-1)<n) && IsPrime((2^p)-1))
        cout<<endl<<((2^p)-1);
    }

This part looks fine but how can I shorten this part?

I want to replace this

    for(unsigned long p=2;p<20;p++)
    {
        if (((pow(2,p)-1)<n) && IsPrime(pow(2,p)-1))
        cout<<endl<<pow(2,p)-1;
    }

To this:

  // Generate integers of the form 2^k-1  
    for (int k=0; k<32; ++k)
    {
        int n = 1;                  // find 2 ^ k
        for (int i=0; i<k; i++)
        {
            n = n * 2;
        }
        n = n - 1;                  // subtract one
        cout << n << endl;
    }