Author Topic: For C programmers...  (Read 11779 times)

Offline Spectre

  • VIP
  • Hero Member
  • **
  • Posts: 622
  • Rank: Unknown
  • Score: Unknown
  • Grossly incandescent
    • Team: No Terrorism
For C programmers...
« on: November 14, 2016, 08:34:20 pm »
I have an assignment in C that is really bugging me, although it seems to be very simple, but I just can't see the solution lol. I need to write a program that will allow the user to check any of the first 4 perfect numbers.

Here's the catch: It must be done using array and while loop (I shouldn't use pre-determined range, something that would display perfect numbers between 1 and 10,000).
The output should be something like this:

"Which perfect number would you like to see? (1 to 4): 3

The 3rd perfect number is 496"

Anyone that can halp?

Offline Ege

  • VIP
  • Hero Member
  • **
  • Posts: 856
  • Rank: Loc
  • Score: 39828
  • |m|
Re: For C programmers...
« Reply #1 on: November 14, 2016, 09:34:15 pm »
Have you tried to format your PC ?

Offline Miau

  • VIP
  • Hero Member
  • **
  • Posts: 565
  • Rank: Jacker
  • Score: 46079
Re: For C programmers...
« Reply #2 on: November 14, 2016, 10:17:50 pm »
I presume you only want 1 array, so it looks a bit more confusing than I'd like. I tried to explain what is stored in each index of the array. I haven't tested it, but it should work, or at least give you some ideas.

Code: [Select]
new pnumb[22];

pnumb[0] = 1; // current number
pnumb[1] = 0; // p numbs found
pnumb[2] = 0; // 1st p numb
pnumb[3] = 0; // 2nd p numb
pnumb[4] = 0; // 3rd p numb
pnumb[5] = 0; // 4th p numb
pnumb[6] = 0; // Remainder
pnumb[7] = 0; // Addition
pnumb[8] = 0; // Divisors found
pnumb[9] = 0; // Divisors (up to 13)
pnumb[10] = 0;
pnumb[11] = 0;
pnumb[12] = 0;
pnumb[13] = 0;
pnumb[14] = 0;
pnumb[15] = 0;
pnumb[16] = 0;
pnumb[17] = 0;
pnumb[18] = 0;
pnumb[19] = 0;
pnumb[20] = 0;
pnumb[21] = 0; // End of divisors.

while(pnumb[1] < 4) // Continues as long as the amount of perfect numbers found is below 4.
{
  for(new i = 1; i < pnumb[0]; i++) // Loops through all the numbers lower than the current number.
  {
    pnumb[6] = pnumb[0] % i; // Divides the current number by i and gets the remainder.
    if(!pnumb[6]) // If the remainder is zero, i is a divisor of the current number.
    {
      pnumb[pnumb[8]+9] = i; // We store i in the array.
      pnumb[8]++; // Adds +1 to the amount of divisors found
    }
  }
  pnumb[7]=0; // Resets the addition to zero.
  for(new i = 0; i < pnumb[8]; i++) // Adds up all the divisors found
  {
    pnumb[7] += pnumb[9+i];
  }
  pnumb[8] = 0; // Resets the amount of divisors found (for the next loop)
  for(new i = 9; i < 22; i++) // Resets all the divisors to zero (for the next loop)
  {
    pnumb[i] = 0;
  }
  if(pnumb[7] == pnumb[0]) // Checks if the addition of all the divisors equals the current number.
  {
  pnumb[pnumb[1]+2] = pnumb[0]; // Stores the current number as a perfect number.
  pnumb[1]++; // Adds 1 to the amount of perfect numbers found.
  }
  pnumb[0]++; // Adds 1 to the current number, to loop again with the next one.
}

/* So your perfect numbers are:
pnumb[2], pnumb[3], pnumb[4], pnumb[5]
« Last Edit: November 14, 2016, 10:54:05 pm by Mia »
Oh! I don't want to fight you, Jorah the Andal. What do I have to gain? If I win, I'm the shit who killed an old man. If I lose, I'm the shit who was killed by an old man.

~ Daario Naharis

Offline Carg

  • VIP
  • Hero Member
  • **
  • Posts: 1506
  • Rank: Homeboy
  • Score: 17525
Re: For C programmers...
« Reply #3 on: November 14, 2016, 10:19:57 pm »
Have you tried to format your PC ?
might work

Offline Quido

  • Head Admin
  • Hero Member
  • *****
  • Posts: 885
  • Rank: Banger
  • Score: 27783
Re: For C programmers...
« Reply #4 on: November 14, 2016, 10:48:11 pm »

Offline Spectre

  • VIP
  • Hero Member
  • **
  • Posts: 622
  • Rank: Unknown
  • Score: Unknown
  • Grossly incandescent
    • Team: No Terrorism
Re: For C programmers...
« Reply #5 on: November 14, 2016, 11:27:40 pm »
I presume you only want 1 array, so it looks a bit more confusing than I'd like. I tried to explain what is stored in each index of the array. I haven't tested it, but it should work, or at least give you some ideas.

Code: [Select]
new pnumb[22];

pnumb[0] = 1; // current number
pnumb[1] = 0; // p numbs found
pnumb[2] = 0; // 1st p numb
pnumb[3] = 0; // 2nd p numb
pnumb[4] = 0; // 3rd p numb
pnumb[5] = 0; // 4th p numb
pnumb[6] = 0; // Remainder
pnumb[7] = 0; // Addition
pnumb[8] = 0; // Divisors found
pnumb[9] = 0; // Divisors (up to 13)
pnumb[10] = 0;
pnumb[11] = 0;
pnumb[12] = 0;
pnumb[13] = 0;
pnumb[14] = 0;
pnumb[15] = 0;
pnumb[16] = 0;
pnumb[17] = 0;
pnumb[18] = 0;
pnumb[19] = 0;
pnumb[20] = 0;
pnumb[21] = 0; // End of divisors.

while(pnumb[1] < 4) // Continues as long as the amount of perfect numbers found is below 4.
{
  for(new i = 1; i < pnumb[0]; i++) // Loops through all the numbers lower than the current number.
  {
    pnumb[6] = pnumb[0] % i; // Divides the current number by i and gets the remainder.
    if(!pnumb[6]) // If the remainder is zero, i is a divisor of the current number.
    {
      pnumb[pnumb[8]+9] = i; // We store i in the array.
      pnumb[8]++; // Adds +1 to the amount of divisors found
    }
  }
  pnumb[7]=0; // Resets the addition to zero.
  for(new i = 0; i < pnumb[8]; i++) // Adds up all the divisors found
  {
    pnumb[7] += pnumb[9+i];
  }
  pnumb[8] = 0; // Resets the amount of divisors found (for the next loop)
  for(new i = 9; i < 22; i++) // Resets all the divisors to zero (for the next loop)
  {
    pnumb[i] = 0;
  }
  if(pnumb[7] == pnumb[0]) // Checks if the addition of all the divisors equals the current number.
  {
  pnumb[pnumb[1]+2] = pnumb[0]; // Stores the current number as a perfect number.
  pnumb[1]++; // Adds 1 to the amount of perfect numbers found.
  }
  pnumb[0]++; // Adds 1 to the current number, to loop again with the next one.
}

/* So your perfect numbers are:
pnumb[2], pnumb[3], pnumb[4], pnumb[5]

Thanks for the reply, that looks good, but it's kinda too advanced from my point of view. I've been using a counter for the while loop and it's working to an extent... Except that I'm getting numbers around 2 million no matter what I type xD (The error message when you enter 0 or a number higher than 4 is working, hooray!)
The most frustrating thing is that I've scoured internet and found nothing like the program I should write lmao...

Have you tried to format your PC ?

Tried it, works fine!

Two great videos on perfect numbers:

https://www.youtube.com/watch?v=T0xKHwQH-4I

https://www.youtube.com/watch?v=q8n15q1v4Xo

Thanks, but that's not what I'm looking for :P

Offline TreePuncher

  • VIP
  • Full Member
  • **
  • Posts: 118
  • Rank: Unknown
  • Score: Unknown
Re: For C programmers...
« Reply #6 on: November 15, 2016, 01:12:08 am »
Code: [Select]
#include<stdio.h>
#include<Math.h>
#define MAX 20
double Primes[MAX];
int main()
{
int o = 0, num = 2, input;
while(o < MAX)
{
if(isPrime(num))
{
Primes[o] = num;
o++;
}
num++;
}
//Off to the equation
printf("Type a number within 1 and %i: ", MAX);
scanf("%i", &input);

printf("The %i perfect number is: %.0lf", input,
(pow(2, Primes[input-1]-1) * (pow(2, Primes[input-1])-1))); //Equation for perfect numbers
return 0;
}
int inline isPrime(int n) //Inline isn't really necessary, I just added it to try to make this faster
//btw2 I stole this from a php code kek
{
int i = 2;
if (n == 2) //Simple enough, 2 is prime, so yeah
{
return 1;
  }
  while (i <= sqrt(n))
{
    if (n % i == 0)
{
    return 0;
    }
    i++;
  }
  return 1;
}
I didn't really have time to comment on it. So if you actually have any questions, feel free to ask.
:D
Btw, double can take huge numbers, but it doesn't take HUUUUUUGE numbers.
If you want to make something at that range (1 to 10000), you'll probably need a library that works with big numbers. As far as I tested, the program will only go as far as the 97th perfect number.
« Last Edit: November 15, 2016, 01:18:08 am by TreePuncher »

Another normal day at Hueland.

Offline Spectre

  • VIP
  • Hero Member
  • **
  • Posts: 622
  • Rank: Unknown
  • Score: Unknown
  • Grossly incandescent
    • Team: No Terrorism
Re: For C programmers...
« Reply #7 on: November 15, 2016, 01:40:15 am »
Code: [Select]
#include<stdio.h>
#include<Math.h>
#define MAX 20
double Primes[MAX];
int main()
{
int o = 0, num = 2, input;
while(o < MAX)
{
if(isPrime(num))
{
Primes[o] = num;
o++;
}
num++;
}
//Off to the equation
printf("Type a number within 1 and %i: ", MAX);
scanf("%i", &input);

printf("The %i perfect number is: %.0lf", input,
(pow(2, Primes[input-1]-1) * (pow(2, Primes[input-1])-1))); //Equation for perfect numbers
return 0;
}
int inline isPrime(int n) //Inline isn't really necessary, I just added it to try to make this faster
//btw2 I stole this from a php code kek
{
int i = 2;
if (n == 2) //Simple enough, 2 is prime, so yeah
{
return 1;
  }
  while (i <= sqrt(n))
{
    if (n % i == 0)
{
    return 0;
    }
    i++;
  }
  return 1;
}
I didn't really have time to comment on it. So if you actually have any questions, feel free to ask.
:D
Btw, double can take huge numbers, but it doesn't take HUUUUUUGE numbers.
If you want to make something at that range (1 to 10000), you'll probably need a library that works with big numbers. As far as I tested, the program will only go as far as the 97th perfect number.

Yep, that's the closest thing to what I need, thanks man! :D

No arrays tho. Also, this inline thingy is a bit confusing, but I'll get around to what it does and means lol

Offline YoMama

  • VIP
  • Hero Member
  • **
  • Posts: 638
  • Rank: Hoodsta
  • Score: 24630
Re: For C programmers...
« Reply #8 on: November 15, 2016, 06:12:55 am »
Also, this inline thingy is a bit confusing, but I'll get around to what it does and means lol
Inline avoids a number of steps that modular programming necessitates but which hurt performance. It does this by directly substituting the function with its body where it would otherwise be called (if possible). It's sort of like a macro, except the compiler chooses between substitution or using the usual call. If there isn't a function call, otherwise necessary stack popping and pushing is avoided, as well as jumps which would cause a pipeline stall*. What exactly inline avoids is not really as important as the instructions per iterations you save going through the loop. If each function call adds, let's say, 10 instructions, then inline allows you to avoid that overhead by not calling. If you have only a function call in your loop and your function has 5 instructions, this cuts out (10 call inst) / (15 inst total) = ~66% of your instruction time through the loop- theoretically, your program will run in 33% of the time, or 200% faster! (It's not this simple in practice.)

However, inline is kind of pointless for this use- since the function is "called" (it's not really called, since it's inline) only once, you might as well eliminate the IsPrime function entirely and move its body to where it's being called in a functionally equivalent way. This would also force the substitution instead of hoping the compiler will be able to do it. Basically, you're doing the inlining yourself.

Code: [Select]
#include<stdio.h>
#include<Math.h>
#define MAX 20
double Primes[MAX];
int main()
{
int o = 0, num = 2, input;
while(MAX > o)
{
                int i = 2;

        if (2 == num) //Simple enough, 2 is prime, so yeah
{
Primes[o] = num;
o++;
}
                while (sqrt(num) <= i)
        {
            if (num % i == 0)
        {
            break;
             }
             i++;
           }

          Primes[o] = num;
        o++;
num++;
}
//Off to the equation
printf("Type a number within 1 and %i: ", MAX);
scanf("%i", &input);

printf("The %i perfect number is: %.0lf", input,
(pow(2, Primes[input-1]-1) * (pow(2, Primes[input-1])-1))); //Equation for perfect numbers
return 0;
}
I haven't tested this, but I hope it gives you the gist of what inline does. Also, a little C tidbit- notice I flipped some of the conditions around. I try to write my conditions with the constant on the left, so if you forget a "=", it doesn't try to assign instead of comparing. If you write if(2 = num), you'll get a clear compiler error. If you write if(num = 2), the problem will be harder to figure out.


*Modern CPUs step different parts of an instruction through each part of the CPU concurrently, like you step your clothing through the wash-dry-fold process of doing laundry. A pipeline stall caused by a jump (function call) is roughly equivalent in this analogy to having to pull out all your clothing and run them through again, so you lose the time you invested in the two loads that were running consecutively with the one that caused the jump. Since modern CPUs have a bunch of stages, the instruction time lost from these cancelled stages can be costly.
« Last Edit: November 15, 2016, 06:52:49 am by YoMama »

Offline Altus_Demens

  • Admin
  • Hero Member
  • ****
  • Posts: 1119
  • Rank: Hoodsta
  • Score: 23951
Re: For C programmers...
« Reply #9 on: November 15, 2016, 11:57:35 am »
Good job everyone. :)

Spectre, next time better show us your code, even if it incomplete and inaccurate, instead of waiting for the solution. It would be much more useful. ;)

Like Tree and YoMama, I solved it using Mersenne primes, if you are interested, here is my code, though you won't find much new in comparison with other solutions above. I used 8-byte integer (unsigned long long int), which is the biggest integer type natively supported by gcc; so perfect numbers up to 8th can be stored there. According to your conditions, I used a single array (with named indices though) and only 'while' loops.
Code: [Select]
#include <stdio.h>
#include <math.h>

#define NUMBER 0
#define CTR 1
#define PRIME_CTR 2
#define MERSENNE_CTR 3
#define PRIME_UPPER 4
#define MERSENNE_NUM 5

int main() {
    unsigned long long int arr[6] = { 0, 0, 2, 0, 0, 0 };
   
    do {
        printf("Which perfect number would you like to see? (1-8)\n");
        fflush(stdin);
    }
    while (!scanf("%llu", &arr[NUMBER]) || arr[NUMBER] == 0 || arr[NUMBER] > 8);
   
    while (arr[MERSENNE_CTR] < arr[NUMBER]) {
        arr[PRIME_UPPER] = sqrt(arr[CTR]) + 2;
        arr[PRIME_CTR] = 2;
        while (arr[PRIME_CTR] < arr[PRIME_UPPER]) if (arr[CTR]%arr[PRIME_CTR]++ == 0) break;
        if (arr[PRIME_CTR] == arr[PRIME_UPPER]) {   
            arr[MERSENNE_NUM] = pow(2, arr[CTR]) - 1;
            arr[PRIME_UPPER] = pow(2, arr[CTR]/2);
            arr[PRIME_CTR] = 2;
            while (arr[PRIME_CTR] < arr[PRIME_UPPER]) if (arr[MERSENNE_NUM]%arr[PRIME_CTR]++ == 0) break;
            if (arr[PRIME_CTR] == arr[PRIME_UPPER]) arr[MERSENNE_CTR]++;
        }
        arr[CTR]++;
    }
    printf("Perfect number #%llu: %llu.\n", arr[NUMBER], arr[MERSENNE_NUM]*((unsigned long long int) pow(2, arr[CTR] - 2)));
   
    system("PAUSE");
    return 0;
}

P.S. Great job explaining inline functions, YoMama, very informative and accurate. I would only add that by default the compiler can ignore inline keyword (and it does ignore it in most cases) and vice versa: it can make functions inline when it's really needed. To force inline, you can use __attribute__((always_inline)) keyword. The difference can be perfectly shown if you take a look at assembly code:
Code: [Select]
<inline __attribute__((always_inline))> int foo(int bar) {
    return bar + 10;
}

int main() {
    printf("%d", foo(5));
    return 0;
}

; 'foo' assembly:
_foo:
addl $10, %eax ; adding 10 to a value stored in %eax
ret ; returning it

; 'main' assembly if 'foo' is forced to be inline:
movl $5, -4(%ebp) ; storing 5 at constant pool
movl -4(%ebp), %eax ; moving constant value to %eax
addl $10, %eax ; adding 10 to the value stored in %eax

; 'main' assembly if 'foo' is not inline:
movl $5, (%esp) ; // storing 5 in stack
call _foo ; // calling _foo with 5 as an argument
This is interesting, but this knowledge is kinda pure academic as you will be rarely messing with inline functions within your real projects.
A paltry man and poor of mind
At all things ever mocks;
For never he knows, what he ought to know,
That he is not free from faults.

Offline Spectre

  • VIP
  • Hero Member
  • **
  • Posts: 622
  • Rank: Unknown
  • Score: Unknown
  • Grossly incandescent
    • Team: No Terrorism
Re: For C programmers...
« Reply #10 on: November 15, 2016, 05:02:14 pm »
@YoMama thanks man, that's a great explanation. It's much clearer now :) If you've got any more suggestions for "amateurs" in C (which I am lol), feel free to post them, or even examples of different interesting codes.

@Altus thanks, but your code is a bit too advanced for the level I'm on (which is a bit more than a beginner). We haven't even touched Mersenne numbers yet, and I doubt we will soon lol xD But anyway, I'm grateful for your input. Yeah, next time I'll post my own code too, should be easier to "debug" it

Offline Altus_Demens

  • Admin
  • Hero Member
  • ****
  • Posts: 1119
  • Rank: Hoodsta
  • Score: 23951
Re: For C programmers...
« Reply #11 on: November 15, 2016, 06:56:56 pm »
You've just probably got confused by their name, Spectre. :)

A Mersenne's prime is a prime number of the form 2^p - 1, where p is also prime. If 2^p - 1 is a Mersenne's prime, 2^(p - 1)*(2^p - 1) would be a perfect number. That's it, nothing complicated. :) Tree's and YoMama's solutions are based on them too as you can see from their code pieces.

The only significant difference between mine and their solution is that I am using an array of 6 elements instead of 6 'normal' variables, and I used only 'while' loop, though 'for' one would fit better.
A paltry man and poor of mind
At all things ever mocks;
For never he knows, what he ought to know,
That he is not free from faults.

Offline Spectre

  • VIP
  • Hero Member
  • **
  • Posts: 622
  • Rank: Unknown
  • Score: Unknown
  • Grossly incandescent
    • Team: No Terrorism
Re: For C programmers...
« Reply #12 on: November 15, 2016, 10:48:21 pm »
You've just probably got confused by their name, Spectre. :)

A Mersenne's prime is a prime number of the form 2^p - 1, where p is also prime. If 2^p - 1 is a Mersenne's prime, 2^(p - 1)*(2^p - 1) would be a perfect number. That's it, nothing complicated. :) Tree's and YoMama's solutions are based on them too as you can see from their code pieces.

The only significant difference between mine and their solution is that I am using an array of 6 elements instead of 6 'normal' variables, and I used only 'while' loop, though 'for' one would fit better.

I understand that, and I'm telling you we didn't even remotely mention "Mersenne" :) Nevertheless, I didn't say your code was bad, I just said it was a bit too advanced for now (from my point of view).

Offline Quido

  • Head Admin
  • Hero Member
  • *****
  • Posts: 885
  • Rank: Banger
  • Score: 27783
Re: For C programmers...
« Reply #13 on: November 15, 2016, 10:58:03 pm »
Yeah, I know they had nothing to do with programming but they are still interesting :p

Offline Miau

  • VIP
  • Hero Member
  • **
  • Posts: 565
  • Rank: Jacker
  • Score: 46079
Re: For C programmers...
« Reply #14 on: November 16, 2016, 12:10:37 am »
You've just probably got confused by their name, Spectre. :)

A Mersenne's prime is a prime number of the form 2^p - 1, where p is also prime. If 2^p - 1 is a Mersenne's prime, 2^(p - 1)*(2^p - 1) would be a perfect number. That's it, nothing complicated. :) Tree's and YoMama's solutions are based on them too as you can see from their code pieces.

The only significant difference between mine and their solution is that I am using an array of 6 elements instead of 6 'normal' variables, and I used only 'while' loop, though 'for' one would fit better.

I understand that, and I'm telling you we didn't even remotely mention "Mersenne" :) Nevertheless, I didn't say your code was bad, I just said it was a bit too advanced for now (from my point of view).

Mersenne numbers have nothing to do with programming. It's just a mathematical concept that is helpful to find perfect numbers. You can find them like that, or like I did (find the divisors of every number, in except for the number itself, and check if their addition equals the number, definition of perfect number).
Oh! I don't want to fight you, Jorah the Andal. What do I have to gain? If I win, I'm the shit who killed an old man. If I lose, I'm the shit who was killed by an old man.

~ Daario Naharis