Learning Java

[Caprico]

Okay, so I just started learning Java, and I'm practicing basic logic by doing problems of ProjectEuler (http://projecteuler.net/about), and I need some suggestions:

There are quite a few problems in there, that require me to analyze a certain number (often more than 100digits long), or a certain pattern of numbers like (http://projecteuler.net/problem=18).. And more than often, the number is too large for my compiler to recognize, and also, I don't know how to feed the pattern or grid or whatever to my program. I guess I'd have to make it read from a text file, but I don't know how to, either in C++ or Java.. So can someone please help me out?

P.S. - I've tried reading articles for reading .txt files on this site, and others, but didn't understand much. And trust me, I really tried. So baby steps would be nice.. Also, can someone please direct me to a good Java forum, much alike this one?

Thanks in advance! :)

[hamsterman]

For huge numbers you can use BigInteger class in Java, or download http://gmplib.org/ for c++.
I don't see what the problem is with reading files. It's just open, read, close.. Could you be more specific about what confuses you?
As for a Java forum, http://stackoverflow.com/ is a great forum for all languages.

[Caprico]

1)I guess I should have specified my problem:

//What is the largest prime factor of the number 600851475143 ?

class Prob3
{
	public static void main()
	{
		long i, j, ans, k=600851475143;
		boolean check=true;

		for (i=1; i<=k; i++)
		{
			if (k%i==0)       //Checks if i is a factor of k
			{
				for (j=2; j<i; j++)        //Checks if i is prime
				{
					if (i%j==0)
					check=false;
				}

				if (check==true)
				ans=i;
			}
		}
		System.out.println((ans)+" is the answer!");     //Prints the answer
	}
}

Compiler error: Integer number too large: 600851475143.
How do I correct this? The problem is not because the number is out of range.. Its some other reason I'm not familiar with yet..

2) How do I read the file? & how exactly does my program see the file? What role do newlines, spaces, commas play in my txt file? How do I read a file line by line? If the info in the file is in the form of a triangle like:

75
95 64
17 47 82
18 35 87 10
20 04 82 47 65
19 01 23 75 03 34
88 02 77 73 07 63 67
99 65 04 28 06 16 70 92
41 41 26 56 83 40 80 70 33
41 48 72 33 47 32 37 16 94 29
53 71 44 65 25 43 91 52 97 51 14
70 11 33 28 77 73 17 78 39 68 17 57
91 71 52 38 17 14 91 43 58 50 27 29 48
63 66 04 68 89 53 67 30 73 16 69 87 40 31
04 62 98 27 23 09 70 98 73 93 38 53 60 04 23

What's the best way to read a file like this? What if I want to feed/convert it into a 2D array?

(Should I make a topic specifically for this problem? I just felt it wouldn't be right to ask Java probs in a C++ Forum..)

[Stewbond]

Well in C++, a long is 4 bytes and has a range of -2,147,483,647 to +2,147,483,647.

An unsigned long is similar but the range is translated to 0 to 4,294,967,296.

A long long has 8 bytes which has a range of -9223372036854775808 to 9223372036854775808.

Java must have a similar container to long long. Especially if it is going to support 64-bit programming.


For fileIO, I definitely don't know anything about java. In c++ we can use getline() to put an entire line into a string. Then we stick that string into a stringstream and if we try and output from a stringstream to another string, it will give us one element at a time (seperated by whitespaces).

[Peter87]

Try adding an L after the number: long i, j, ans, k=600851475143L;

[JLBorges]

> Well in C++, a long is 4 bytes and has a range of -2,147,483,647 to +2,147,483,647

Surely these are implementation-defined quantities.

In C++, a long is sizeof(long) bytes in size and has a range of std::numeric_limits<long>::min() to std::numeric_limits<long>::max().



> What is the largest prime factor of the number 600851475143 ?

I suppose the ProjectEuler folks expect the use of some prime factorization algorithm.
http://en.wikipedia.org/wiki/Integer_factorization

A reasonable algorithm for a small number like 600851475143 would be:
a. Find all prime numbers up to the square root of the number (say, by a sieve algorithm)
b. Check for divisibility.

Well, I had some time to kill, so here's some C++(11) code:

#include <vector>
#include <type_traits>
#include <cmath>
#include <cstdint>
#include <iostream>
using namespace std ;

// sieve of sundaram (naive implementation)
template< typename INTEGER >
vector< typename enable_if< is_integral<INTEGER>::value, INTEGER >::type >
    generate_primes_till( INTEGER N )
{
    const INTEGER M = N / 2 ;
    std::vector<bool> sieve( M, true ) ;
    for( INTEGER i = 1 ; i < M ; ++i )
    {
        const INTEGER L = (M-i) / ( 2*i + 1 ) ;
        for( INTEGER j = i ; j <= L ; ++j )
            sieve[ i + j + 2*i*j ] = false ;
    }

    std::vector<INTEGER> primes ;
    primes.push_back(2) ;
    for( INTEGER i = 1 ; i < M ; ++i )
        if( sieve[i] ) primes.push_back( i*2 + 1 ) ;
    return primes ;
}

int main()
{
    const std::int_fast64_t n = 600851475143LL ;
    const auto primes = generate_primes_till<std::int_fast32_t>( std::sqrt(n) + 1 ) ;

    for( auto iter = primes.rbegin() ; iter != primes.rend() ; ++iter )
        if( ( n % *iter ) == 0 )
        {
            std::cout << *iter << '\n' ;
            break ;
        }
}

[hamsterman]

How do I read the file? & how exactly does my program see the file? What role do newlines, spaces, commas play in my txt file? How do I read a file line by line?

A file, like anything else in a computer, is a sequence of bytes. If it's a text file, the value of each byte represents some character (it's ASCII I'm talking about. Unicode is a bit more complicated). For example, 97 is 'a', 32 is a white space and 13 followed by 10 marks the end of a line (you don't need to know these). Reading the file byte by byte yourself would be a bit of a pain, so there are libraries meant to make it more comfortable for you.

Now, about your example.. The key to successfully reading the contents of a file is knowing what they look like and knowing how you want to store them. You need to analyse each case separately. If you know that the numbers form a triangle, assuming that you want to have a vector of vectors of numbers, you'd do

fstream file("myfilename");//open the file
vector<vector<int> > contents;
for(int line = 1; !file.fail(); line++) {//while you can read from the file.. (used a for loop to count the lines)
   vector<int> line_contents;
   for(int num = 0; num < line; num++) {//there are n numbers on the nth line
      int val;
      file >> val;//read a number
      line_contents.push_back(val);//save it
   }
   contents.push_back(line_contents);//save the line
}

Although when your file is simple like that, you can use a bit of trivial maths instead.

vector<int> contents;
int val;
while(file >> val)//while you can successfully read..
   contents.push_back(val);

//now the number on line i (starting from 0) and position j (also from 0) is at
contents[i*(i+1)/2+j];

Operator >> (when it's argument is a number) will discard and number of white spaces or tabs or newlines until it finds a number and stop at the end of that number. If there was a word instead of a number, tho operation would fall (this is not the case with a sting argument).

Now, if you wanted to make a vector of vectors of numbers and didn't know how many numbers there would be, the algorithm would become more ugly. Even worse if not all entries had to be numbers.. (The plan is to use std::getline from <string> and std::stringstream from <sstream>. I won't get into details, as the post is getting lengthy..)

edit: I just realised the first code snippet will read one line with a single garbage number. That's because even if >> fails (due to end of file), I still push the number it (didn't) read into line_contents and then contents. What is needed is to exit the nested loops. That could be done by prefixing the push_backs with if (!file.fail()) or simply a goto.

[Caprico]

@Stewbond, corresponding data type for long long in Java is long, and I'm already using that type.. Like I said, the problem is not in the range, but in the initialization process... It refuses to accept that large a number explicitly.

@ Peter87, that worked!!! Please explain! I didn't get a compiler error.. However, the program does not give a result.. Almost as if it got stuck in an infinite loop..

@JLBorges - I want a speed/memory efficient program.. This is just the 3rd program, I don't think it would have that difficult a solution.. Anything more.. elegant? Or even brute force would do.. I'm concerned with the logic... I can optimize the codes later... Also, didn't understand a word of your program.. :( Not at all well-versed in C11..

[Peter87]

Caprico wrote:

@ Peter87, that worked!!! Please explain! I didn't get a compiler error..

The L makes the number a long. Without the L it is an int and since the number was too big to be stored in an int you got an error.

Caprico wrote:

However, the program does not give a result.. Almost as if it got stuck in an infinite loop..

Can't it just be that the code takes very long time to run?

[JLBorges]

> I'm concerned with the logic...

The logic is extremely simple. Reproduced here once again:

A reasonable algorithm for a small number like 600851475143 would be:
a. Find all prime numbers up to the square root of the number (say, by a sieve algorithm)
b. Check for divisibility.

Forget the C++ code; try implementing the algorithm in Java. You might want to have a look at:
http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes
http://introcs.cs.princeton.edu/java/14array/PrimeSieve.java.html

[Caprico]

@Peter87, but I declared that variable as a long... Why do I explicitly need to add an L? And no, I kept that program running for an hour, no result.. And I've tried more difficult and ugly problems.. They gave me the answer in 5mins max, however inefficient and mindless my program was.. So..

@JLBorges
> Find all prime numbers up to the square root of the number
It took me a while to figure out why "square root".. I have a lot to learn in logic it looks like!

@hamsterman
Thank you for that explanation... I understood the basics of it.. Now the biggest issue with me is that in my college, we didn't have vectors or file input/output in the syllabus.. Neither in C++ nor Java (Don't ask, they asked us to work with TurboC++, where we still use .h headers.. I guess that's good enough a sign to show the standard of programming we're taught)..
So I'm still new to ifstream, file.fail, push_back, and all such terms... I'll need to experiment with those stuffs when I get free time.. For the time being, this much is pretty good for my understanding...

Thanks all you guys! :D Helped a lot...

[Peter87]

Caprico wrote:

but I declared that variable as a long... Why do I explicitly need to add an L?

The variable is not the problem. The problem is that when you write numbers in a row like this 600851475143 it has the type int. Adding an L after makes it type long. 600851475143 is too big to be stored in an int, that's why you have to make it a long. I don't know why Java can't make it a long automatically but I guess they think it is better to be explicit to avoid mistakes.

Caprico wrote:

I kept that program running for an hour, no result..

When I run your program and set k=100000000 it takes about 13 seconds. The number 600851475143 is about 6000 times as big as 100000000 so a guess is that it takes 6000 * 13 = 78000 seconds to run. That is more than 21 hours! This is just an approximation but should show you that it takes time.

[Caprico]

Wow, that makes sense... So can you suggest an efficient way to do this problem? Further ahead on the site, there are bigger numbers and more complex situations... I can't keep my program running that long! Also, I'm just a student.. C++ was my first programming language, and Java is my second, and I'm master in neither.. I just have a profound love for it, as well as mathematics, which makes ProjectEuler somewhat like Utopia for me.. :P But I still am amateur when it concerns elegance in the program, or efficiency.. I have a fair bit of good logic to be modest.. But still, I want to be able to do such problems without breaking a sweat.. One or two challenges along the way is good.. Could someone please check that site out, review it, and tell me if I'm doing good, or if I should be faster?
Also any suggestions how I can keep track of progress my program is making? Like, any way to show how close it is to the end, or when it reaches the half mark or 1/4th mark or something? Also, how do I break a non-responding/infinite program on the console? Something analogous to pause-break?

[hamsterman]

A different algorithm (pseudo code)

number = 600851475143
factor = 2
while factor < number
   if number % factor = 0, then
      number = number / factor
      //now factor is a prime factor, not smaller than any you've found before
   else factor ++
end

This should be significantly faster, although I haven't tested. The idea is to find the smallest prime factor and remove it. That way after the loop, number will be the largest prime factor of input number.
It might be a good plan to deal with factor = 2 case separately and do factor += 2 instead of factor ++.

[Caprico]

Wow.. That's a good idea... I'll try that! Thanks! :D

how do I break a non-responding/infinite program on the console? Something analogous to pause-break?

Please, some solution to this?

[Caprico]

hamsterman, that was brilliant.. Took less than a second to give me the answer! Thanks a lot!