divisors
my code is supposed to print highly composite numbers below 100, which are 1,2,4,6,12,24,36,48,60.
each number has more divisors than any number lower than it, for example 4 has 3 divisors, 3 has 2 divisors, 2 has 2 divisors, 1 has 1. so 4 is "highly composite".
my code unfortunately prints out all numbers below 100, can anyone show me what i've done wrong?
class HighlyCompositeNumbers{
publicstaticvoid main(String[] args){
for(int num = 1; num<100; num++){
if(testIfHighlyComposite(num)) System.out.print(num+" ");
}
}
staticboolean testIfHighlyComposite(int num){
int count = 0;boolean highlyComposite =true;
for(int divisor = 1; divisor <=num; divisor++){//get divisor count of num.
if(num%divisor == 0) count++;
}
for(int x = num-1; x >0; x=x-1){//test count of divisors for numbers
if(divisorCount(x) > count){//lower than num.
highlyComposite =false;
break;
}
}
if(highlyComposite =true)returntrue;
elsereturnfalse;
}
staticint divisorCount(int x){
int count = 0;
for(int divisor = 1; divisor <=x; divisor++){
if(x%divisor == 0) count++;
}
return count;
}
}
[3068 byte] By [
mark_8206a] at [2007-11-27 4:19:03]
This is wrong:// ...
if(highlyComposite = true) return true;
else return false;
// ...
and this is also incorrect:if(divisorCount(x) > count)
prome, i haven't worked out what i've done wrong yet, but i'll probably get it soon.is there any chance you could show me how you would go about doing the same code, so i could try learn from it?
> prome, i haven't worked out what i've done wrong yet,
> but i'll probably get it soon.
>
> is there any chance you could show me how you would
> go about doing the same code, so i could try learn
> from it?
I'll give you the first error. It's not
if(highlyComposite = true) return true; // you're assigning true to highlyComposite every time
else return false;
butif(highlyComposite == true) return true; // notice the '==' instead of '='
else return false;
But since the highlyComposite is already a boolean, you can just return that value at once.
Now try to spot the second error yourself.
Good luck.
i changed the boolean part from = to == and i noticed that the output is now almost correct, but i still can't figure out what's wrong with that other line.
> i changed the boolean part from = to == and i noticed
> that the output is now almost correct, but i still
> can't figure out what's wrong with that other line.
I already told you what the second error is. Carefully re-read the definition of a highly composite number, and/or do as I suggested in numerous threads of yours: debug your code.
; )
>
> I already told you what the second error is.
> Carefully re-read the definition of a highly
> composite number, and/or do as I suggested in
> numerous threads of yours: debug your code.
> ; )
prome, if you had to write code to print highly composite numbers, could you show me how you would do it? (i assume it would be much better than mine).
> ...> prome, if you had to write code to print highly> composite numbers, could you show me how you would do> it? (i assume it would be much better than mine).I'll show you mine if you show me yours!; )
> I'll show you mine if you show me yours!
lol ok! i managed to solve the other problem
so here it is
class HighlyCompositeNumbers {
//A highly composite number is a positive integer which has more divisors
//than any positive integer below it.
public static void main(String[] args) {
System.out.println("Highly Composite Numbers below 1000: ");
for(int num = 1; num <1000; num++) {
if(testIfHighlyComposite(num)) System.out.print(num+" ");
}
}
static boolean testIfHighlyComposite(int num) {
int count = 0; boolean highlyComposite = true;
for(int divisor = 1; divisor <=num; divisor++) {
if(num%divisor == 0) count++;
}
for(int x = num-1; x >0; x=x-1) {
if(divisorCount(x) >= count) { //greater than or equal to count.
highlyComposite = false;
break;
}
}
if(highlyComposite == true) return true;
else return false;
}
static int divisorCount(int x) {
int count = 0;
for(int divisor = 1; divisor <=x; divisor++) {
if(x%divisor == 0) count++;
}
return count;
}
}
> > I'll show you mine if you show me yours!
>
> lol ok! i managed to solve the other problem
> so here it is
> ...
Well done.
I only have two remarks.
1 - you calculate the number of divisors of a certain number twice in your code: there is no need to do this twice. Instead of doing:int count = 0;
boolean highlyComposite = true;
for(int divisor = 1; divisor <=num; divisor++) {
if(num%divisor == 0) count++;
}
you could just do:int count = divisorCount(num);
boolean highlyComposite = true;
and
2 - No need for such a statement:if(highlyComposite == true) return true;
else return false;
this can be written as:return highlyComposite;
Here's how I did it:
public class HighlyCompositeNumbers {
static boolean isHighlyComposite(int n) {
int divisorsOfN = numberOfDivisors(n);
for(int i = 1; i < n; i++) {
if(divisorsOfN <= numberOfDivisors(i)) return false;
}
return n > 0;
}
static int numberOfDivisors(int n) {
int divisors = 1;
for(int i = 2; i <= n; i++) {
if(n%i == 0) divisors++;
}
return divisors;
}
public static void main(String[] args) {
for(int n = 0; n < 1000; n++) {
if(isHighlyComposite(n)) System.out.print(n+" ");
}
}
}
> much appreciated!You're welcome, as usual.
Unless you actually need an isHighlyComposite method, you may as well get a quadratic speed increase* by only counting divisors for each number once. Dynamic programming at its most basic.
It's also easy to get a quadratic speed increase* in countDivisors by exploiting the simple property that if a divides b then (b/a) divides b.
The resulting code is public class HighlyCompositeNumbers
{
public static void main(String[] args) {
int max=0;
for (int i=1; i<100; i++) {
int count=countDivisors(i);
if (count>max) {
System.out.println(i);
max=count;
}
}
}
private static int countDivisors(int n) {
if (n<2) return n;
int count=2;
int i=2;
while (true) {
int isqr=i*i;
if (isqr>n) return count;
if (isqr==n) return count+1;
if (n%i==0) count+=2;
i++;
}
}
}
* If N is the bound up to which to search, the first improvement is from O(N^2) countDivisors calls to O(N) countDivisors calls. The second improvement takes countDivisors(n) from O(n) to O(sqrt(n)). The net result is that the algorithm is reduced from O(N^3) to O(N sqrt(N)).
just seen your code, thanks YAT
