## Nice competition => Math + programming

Post any maths and/or physics related questions here.

Moderators: Darobat, RecursiveS, Dante Shamest, Bugdude, Wizard

Kybo Ren wrote:Speaking of numbers, is
"unociento" correct?
I think you are supposed to say "ciento", but since you say "doscientos" is "unociento" acceptable?

No, the acceptable Spanish words for "one hundred" are "cien" (most common) and "ciento" (obsolete).

Alvaro
Moderator

Posts: 5185
Joined: Mon Sep 22, 2003 4:57 pm
Location: NY, USA

How can I do the problems that need huge numbers...? I have this for problem 20:

Code: Select all
`#include<iostream>__int64 factorial(int n){   __int64 prod = n;   while(n)      prod *= --n;   return prod;}int main(){   std::cout << factorial(100);   std::cin.get();}`

It should find the factorial of 100, but all I get is 0.

EDIT: Same thing for problem 10:
Code: Select all
`#include <iostream>bool isprime(long int n){   if(n==2)      return true;   int cnt = 0;   for(int i = 2; i < n; i++)      if(n%i==0)         cnt++;   return cnt==0;}int main(){   long int total = 0;   for(long int i = 1; i <= 1000000; i++) {      if(isprime(i))         total += i;   }   std::cout << total;   std::cin.get();}`

If it wasn't for C, we would be using BASI, PASAL and OBOL.

tomcant

Posts: 3101
Joined: Tue Sep 23, 2003 1:56 am
Location: Colchester, UK

100! (factorial) is way too big to fit in a 64-bit unsigned.
If you want to do it by yourself: make a big array of unsigned chars (size 200 would suffice for 100!), then fill in the digits.

You could also use Miracl, like Kybo Ren suggested, but that's no fun!
Togra

Posts: 188
Joined: Wed Jul 28, 2004 8:51 am
Location: NL

Togra wrote:100! (factorial) is way too big to fit in a 64-bit unsigned.
If you want to do it by yourself: make a big array of unsigned chars (size 200 would suffice for 100!), then fill in the digits.

You could also use Miracl, like Kybo Ren suggested, but that's no fun!

Thanks.
If it wasn't for C, we would be using BASI, PASAL and OBOL.

tomcant

Posts: 3101
Joined: Tue Sep 23, 2003 1:56 am
Location: Colchester, UK

Alvaro wrote:No, the acceptable Spanish words for "one hundred" are "cien" (most common) and "ciento" (obsolete).

OK, thanks

Maybe you can come over here and help me in Spanish class every day
>.>
<.<
Kybo Ren
C++ Beginner

Posts: 2049
Joined: Wed Feb 11, 2004 9:28 pm

Togra wrote:100! (factorial) is way too big to fit in a 64-bit unsigned.
If you want to do it by yourself: make a big array of unsigned chars (size 200 would suffice for 100!), then fill in the digits.

You could also use Miracl, like Kybo Ren suggested, but that's no fun!

On second thoughts, I can't seem to get Miracl up and running so I need an alternative. Anything else... ?
If it wasn't for C, we would be using BASI, PASAL and OBOL.

tomcant

Posts: 3101
Joined: Tue Sep 23, 2003 1:56 am
Location: Colchester, UK

Im trying to solve Problem 19. Since that I'm new in c++ I don't know any good functions so if you see something in my code that can be improved please say what

This is what I've got this far.

Code: Select all
`#include <iostream>using namespace std;int main(){    int jan = 31;    int feb1 = 28;    int feb2 = 29;    int mars = 31;    int april = 30;    int maj = 31;    int juni = 30;    int juli = 31;    int aug = 31;    int sep = 30;    int okt = 31;    int nov = 30;    int dec = 31;    int ar = 1900;    int dag = 0;    int dag1 = 0;    int feb;    int sundays;    int sundays1;        for(ar; ar < 2001; ar++){        dag += jan;        feb = (ar%4==0 && (ar%100!=0 || ar%400==0)) ? feb2 : feb1;        dag += feb;        dag += mars;        dag += april;        dag += maj;        dag += juni;        dag += juli;        dag += aug;        dag += sep;        dag += okt;        dag += nov;        dag += dec;    }          sundays = dag/7;           dag1 += jan;        feb = (ar%4==0 && (ar%100!=0 || ar%400==0)) ? feb2 : feb1;        dag1 += feb;        dag1 += mars;        dag1 += april;        dag1 += maj;        dag1 += juni;        dag1 += juli;        dag1 += aug;        dag1 += sep;        dag1 += okt;        dag1 += nov;        dag1 += dec;                sundays1 = dag1/7;                cout << sundays - sundays1;                system("pause");        return 0;`

Safari

Posts: 1362
Joined: Sun Sep 19, 2004 11:07 am

Safari, check for example http://www.cplusplus.com/ref/ctime/index.html for built-in C time functions.

Regarding your algorithm: you seem to be counting days and getting the asked number of sundays by dividing by 7, that won't work I'm afraid.
You need to check each first day of the month on being sunday, at least that's what I'd do (if I had time ).

Problem 19 wrote:... twentieth century (1 Jan 1901 to 31 Dec 2000) ...

Is this a typical English thing? I would say the 20th century started at 1 jan 1900 and ended at 31 dec 1999 ...
Togra

Posts: 188
Joined: Wed Jul 28, 2004 8:51 am
Location: NL

Is this a typical English thing? I would say the 20th century started at 1 jan 1900 and ended at 31 dec 1999 ...
Nope... every century starts at xx01 and ends at the end of xy00. So our century will finish on January 1st, 2101.

t i l e x

Posts: 3604
Joined: Wed Dec 03, 2003 3:59 pm

t i l e x wrote:
Is this a typical English thing? I would say the 20th century started at 1 jan 1900 and ended at 31 dec 1999 ...
Nope... every century starts at xx01 and ends at the end of xy00. So our century will finish on January 1st, 2101.

Which is kind of funny once you think about it... seeing as how the year 2000 had these huge worldwide celebrations compared to 2001.
"Given enough time, man can do anything with a bit of string and some Tinker toys." Bruce Bolden, Senior Instructor at the University of Idaho.

leas5040

Posts: 1214
Joined: Mon Apr 12, 2004 9:51 pm
Location: Moscow, ID

leas5040 wrote:Which is kind of funny once you think about it... seeing as how the year 2000 had these huge worldwide celebrations compared to 2001.

Indeed, it's like the first element of your array is at position [1] .
Now let's get ontopic... I'm at 8 percent, haven't done anything in the past month. But I want to finish it, guess I won't succeed in 2 or 3 days like Alvaro... Just need to find time to work on it.
Togra

Posts: 188
Joined: Wed Jul 28, 2004 8:51 am
Location: NL

One piece of advice: don't delete the solution once you finish a problem, because often you can reuse the code for another problem. For instance, there are several problems involving finding factors of numbers and several other problems about finding the path that maximizes some sum of numbers.

Alvaro
Moderator

Posts: 5185
Joined: Mon Sep 22, 2003 4:57 pm
Location: NY, USA

Well , i have a problem with a fairly easy problem !!
Problem #7 : find the 1001th prime number
Code: Select all
`#include <iostream> #include <fstream> using namespace std;bool check_prime(int n){   if ( n!=2 && n%2 == 0 )  return false;   for (int i=3 ; i<=n/3 ; i++)      if ( n%i == 0 ) return false;   return true;}int main() {    ofstream out("Output.txt");       //Problem 7 :   int count = 1 , prime=3;   while ( count <= 1001 )   {      if ( check_prime(prime) == true )  count++;      prime += 2;   }   out << "Problem 7 : The " << count << " Prime Number = " << prime << endl;               return 0; } `

it gives me 7935 but this is wrong !

Blueteeth

Posts: 616
Joined: Thu Sep 25, 2003 9:54 pm
Location: Egypt

Is it because there are (is?) prime numbers before 3?

I know 2 is prime, but I also remember my math teacher saying there was controversy over whether 1 was prime. Can you tell me if 1 is prime, Alvaro?
Kybo Ren
C++ Beginner

Posts: 2049
Joined: Wed Feb 11, 2004 9:28 pm

Blueteeth wrote:it gives me 7935 but this is wrong !

Yep, that would be wrong. You have `prime+=2' after you have already found a prime, so the final value is some prime plus two. You might also have an off-by-one problem (I'm not sure, but those are easy to make in this type of problem). The thing to do is change the program to find the 6th prime, which is easier to verify. Once it's working, change the number back to 1001.

Kybo Ren wrote:Is it because there are (is?) prime numbers before 3?

Well, his counter was initialized to 1, so that takes care of the 2.

I know 2 is prime, but I also remember my math teacher saying there was controversy over whether 1 was prime. Can you tell me if 1 is prime, Alvaro?

Modern math considers that 1 is not a prime. Traditionally it was considered a prime, but it has different enough properties that it's better to call it something else (it's called a unit).

Alvaro
Moderator

Posts: 5185
Joined: Mon Sep 22, 2003 4:57 pm
Location: NY, USA

PreviousNext