sieve of eratosthenes problem -- can't get it to run, dont know where bug is...

[2EwbqMoL]

err

[TheIdeasMan]

although this STILL does not work. at all. the code compiles with no errors or warnings in TDM-GCC using C++ 11 standards, but crashes immediately.

Your array of primes is not initialised at any point (lines 15 and 29 cause all the logic to be missed, all the values a re garbage, not 0 or 1) So that is one big golden rule : "Always initialise your variable to something" :+)

If you want to use the largest possible numbers, consider std::size_t , it is usually the largest unsigned type, on a 64 bit machine it can go up 2⁶⁴-1. Making a type unsigned doubles the extent of the numbers it can store.

I don't see where you are calculating primes. There are some clever ways of doing that. Have a look at the wiki page, there is Euler's :+) method near the bottom. Just don't do trial division. Remember Google and wiki are your friends :+) There is a quick algorithm which involves bitset

With your limit of sqrt(Base) , that is fine for working out primes. If one has removed all the multiples up to sqrt(Base), then all the numbers left up to Base will be prime. But realise you are after factors which are prime. For example 2 * 47 = 94, so there are factors that are bigger than sqrt(Base), if Base was 94 in this example.

The other big thing to remember about PE is that brute force is often not the answer, one has to come with a cunning plan. PE is all about clever algorithms.

In terms of publishing your working code, I wouldn't worry about that too much, especially for the low numbered problems, squillions of people have already completed them. Like any cheating, if one doesn't understand the early questions given the answer, then they won't have a hope with the later questions.

Good Luck !!

[TheIdeasMan]

Also, If your code doesn't work, consider learning to use a debugger - hopefully there is one in your IDE. One can step through code 1 line at a time, keep an eye on the values of your variables, deduce where it all goes wrong. This is a definite skill well worth learning, it will save you days of staring/wondering about your code :+)

With containers, STL ones like std::vector, one can say how many items, and get it to initialise all the items in it to a value. Have a look at the reference material.

See if you can figure out how to use a std::bitset Hint: Use the subscript as the number.

[2EwbqMoL]

hey sorry guys. I tried editing my post and deleted it by mistake somehow.

my code actually DOES work now. I rehauled it again -- but I run into memory issues of some type -- probably stack overflow -- when I use such large numbers as a long long.

it DOES reliably produce the sieve for smaller integers. but with big numbers in the trillions or higher it just crashes instantly, and doing

im not sure how I could use the debugger (especially gdb, switch from VC++ to open source) to help. as im sure its a memory allocation issue -- like I said I probably overflowed the stack trying to generate such a large list of prime numbers and the problem may lie in effeciency.

here is my sieve of eratosthenes as it is now -- I just want it to work with larger numbers. still an accomplishment I guess...

#include <iostream>
#include <cmath>

void sieve(int ubound, int primes[]);

int main()
{
    long long n;
    std::cout << "Input Number: ";
    std::cin >> n;
    if(n<2){
        return 1;
    }
    long long upperbound = sqrt(n);
    int A[upperbound];
    sieve(upperbound, A);
    for(long long i=0; i<upperbound; i++)
    {
        if(A[i] == 1)
            {
                std::cout << " " << i << " ";
            }
    }
    return 0;
}

void sieve(int ubound, int primes[])
{
    long long i, j;
    for(i=0;i<ubound;i++)
    {
        primes[i] = 1;
    }
    primes[0]=0,primes[1]=0;
    for(i=2;i<ubound;i++)
        {
        for(j=i*i; j<ubound;j+=i)
            {
                primes[j]=0;
            }
        }
}

[2EwbqMoL]

ugh, maybe even this one doesnt work. why I dont know, it should. its probably the fact Im using a square root. but hell, im about to quit this project completely and give up for a few months. Im just sick of this going all wrong even though I have the theory down.

its stuff like this that made me always think the whole pseudocode thing was worthless. unless you already have the knowledge and skill to really code it, its just like an outline for an essay -- which I never use. outlines actually make me less capable because I box myself in trying to do things one way I cant. trust me, all my outline essays scored in the 80s, and ehwen I do them on the fly 5 minutes before class and walk in late I get 100 hahahaha.

I know my math, such as that in theory the square root should be close enough to find prime factors, and the i and j statements where it seeks out multiples are right.

its something Im telling the computer to do thats screwing everything up.

and I do know that even if I solved THAT issue, the memory allocation error that crashes it on large calculations would still happen. so I dont even know if I care to finish trying to code this at this point. I feel like throwing in the towel and picking another project...


edit: now I see the math error, I forgot a step after generating the list of prime numbers -- obviously I have to check if it is divisible, which is silly of me. but that still doesnt fix the problem that if I try to generate a list for a gigantic number, the memory makes it crash

[2EwbqMoL]

so I the actually working code for smaller numbers is here (although I still didnt switch long with integers, could be fixed that way but it works...)...

I guess my only question is, can I get this to work with 32 and 64 bit sized integers?

the square root code is never used in this, it is a wasted memory space, but if I can get this to intake and use larger numbers, all will be well and it will function with any set of numbers.

#include <iostream>
#include <cmath>

void sieve(int ubound, int primes[]);

int main()
{
    long long n;
    int i;
    std::cout << "Input Number: ";
    std::cin >> n;
    if(n<2){
        return 1;
    }
    long long upperbound = n;
    int A[upperbound];
    int SquareRoot = sqrt(upperbound);
    sieve(upperbound, A);
    for(i=0; i<upperbound; i++)
    {
        if(A[i] == 1 && upperbound%i==0)
            {
                std::cout << " " << i << " ";
            }
    }
    return 0;
}

void sieve(int ubound, int primes[])
{
    long long i, j, m;
    for(i=0;i<ubound;i++)
    {
        primes[i] = 1;

    }
    primes[0]=0,primes[1]=0;
    for(i=2;i<ubound;i++)
        {
        for(j=i*i; j<ubound;j+=i)
            {
                primes[j]=0;
            }
        }

}

[TheIdeasMan]

If you want to allocate dynamically (on the heap, rather than the stack), the easiest way is to use an STL container, even a std::vector.

But I mentioned using a std::bitset, the reason is that 8 "numbers" are packed into 1 byte, it's like an array, but one can address the individual bits, and set a bit to true if it's subscript is prime false otherwise. That way the memory consumption is much less, and it's still on the heap.

On the other hand a std::vector<int> or an array of int typically occupies 4 bytes for each number, or worse a std::vector<std::size_t> occupies 8 bytes per number, so you could be 64 times better off using the std::bitset

http://www.cplusplus.com/reference/bitset/bitset/
http://en.cppreference.com/w/cpp/utility/bitset

Using sqrt is fine, as I mentioned before.

Btw, which Euler problem is it? Do both the factors have to be prime?

[TheIdeasMan]

.... obviously I have to check if it is divisible, ....

It's problem 3 isn't it? Now I know what the question is ....

You don't have to check if all of them are divisible, once you have the list of prime numbers, start with the largest one and work backwards :+) However the smallest prime is 2, so start from the prime which is just less than or equal to Base/2. This also limits how far you have to go with the prime numbers. So the largest number you need a multiple of is somewhere around sqrt(Base/2)+1

[dhayden]

You'll need to sqrt() if you want to give input numbers in the trillions because you create an array of size N. So if the input is a trillion, you create an array of a trillion ints which will require 4 trillion bytes to store. Do you have that much RAM? Probably not :)

You only need to execute the inner loop of the sieve when i is prime. For example, the first time through the sieve indicates that all even numbers are not prime. When you check 4, there's no need to indicate that multiples of 4 aren't prime because they are also multiples of 2, which you already did.

Don't get frustrated. The whole point of Euler problems is that a simple solution often takes too much memory or too much time. You have to find a clever solution.