Solve Number Puzzle with C and Java

Question

This question is translated into English by me from another forum, I found it interesting and then just write a Java solution. And found there's some heap size problem when dealing with large number like 10000000. And I would like to seek some really smart solution compared with my own.

Original Post is in Chinese. And I kind of revised it a little based on my understanding to make it clearer. http://zhidao.baidu.com/question/1637660984282265740.html?sort=6&old=1#here

Below is the puzzle:

10000 rows of numbers;
1 row: 2,4,6,8...2K(2K<=10000000); (numbers no repeats for this row)
2 row: 3,3,6,6,9,9...3K(3K<=10000000); (starting from this row, each number repeats 2 times and a multiple which has something to do with row number (2XrowNumber-1) to be specificaly)
3 row: 5,5,10,10,15,15...5K(5K<=10000000);
and following 7K,9K,11K,13K....until
10000 row: 19999,19999,39998,39998....19999K,19999K (19999K<=10000000);

That's all the rows to be used in the following part. And now we will calculate the repeat times of numbers starting from row 1 and row 2:

Integer w1 is the repeat times of numbers in row 1 and row2. For example, consider row 1 numbers 2,4,6 and row 2 numbers 3,3,6,6. Then the repeat times up to this point would be 3 since 6 is already in row 1 and appears 2 times in row 2, and 3 appears 2 times in row 2;

Integer w2 is the repeat times of numbers in row 1 and row 2 and row 3. 
Integer w3 is the repeat times of numbers in row 1 and row 2 and row 3 and row 4. 
......
Integer w9999 is the repeat times of numbers of row 1,row 2,row 3 .....row 10000.

And now print out all integers, w1,w2....w9999;

I have come up with one Java solution, but I have heap size problem since 10000000 is too large and the memory is not enough. So I just use 10000 instead of 10000000, and 10 instead of 10000. Below is what I write in Java. I guess it should be right (if not, please point it out):

    Set nums = new HashSet();
    int max = 10000;
    int row = 10;
    for (int i=2;i<=max;i+=2){
        nums.add(new Integer(i));
    }
    int nums_size = nums.size();
    int w = 0;
    for (int i=2;i<=(row);i++){
        int tmp_count = 0;
        int self_count = 0;
        for (int j=(2*i-1);j<=max;j+=(2*i-1)){
            nums.add(new Integer(j));
            self_count++;
            if (nums.size()==nums_size){
                tmp_count++;
            } else {
                nums_size = nums.size();
            }
        }           
        w += tmp_count;
        w += self_count;
        System.out.println("w"+(i-1)+": "+w);
    }

My question is

1. How to get a better solution in Java (if any)?
2. How to do it in C since there would be no Set class in C as I remember. (importing 3rd party library would not be preferred)?

Thanks.

Answer 1

Here is a simplified version of your code. Since it doesn’t use HashSet, creating a C version out of it should be no problem anymore.

int max = 10000;
int row = 10;
boolean[] seen=new boolean[max+1];
for(int i=2;i<=max;i+=2) seen[i]=true;
int w = 0;
for(int i=2;i<=(row);i++) {
    int self_count = 0;
    for(int j=(2*i-1);j<=max;j+=(2*i-1)) {
        self_count++;
        if(seen[j]) w++; else seen[j]=true;
    }
    w += self_count/2;
    System.out.println("w"+(i-1)+": "+w);
}

Answer 2

Not an answer, but a hint: try using least common multiples.

For example, LCM(5,3)=15, and 15 is the first element in both rows 2 and 3. LCM(2,15)=30, and 30 is the first element in each of the first 3 rows.

You'll eventually get to a row r where the LCM of the first element of the first r rows is beyond 10,000,000, at which point no number shows up each of those rows.