[ Solved ]Các bài toán về số.

[aMember]

Mình đang muốn sưu tập 1 số bài toán giải quyết về số ví dụ như : Số nguyên tố, số hoàn hảo, ... , tìm ước chung lớn nhất, giai thừa ... Lập ra đề tài này hi vọng có nhiều người nhiệt tình tham gia, post bài chia sẻ kinh nghiêm, tìm ra những thuật toán tốt nhất, giải quyết các bài toán với những số lớn, thời gian thực hiện tốt nhất có thể. Mình xin mở đầu với mấy bài nhỏ này hi vọng mọi người coi xong giúp đỡ cho ý kiến và chia sẻ những bài của mình lên nhé !
Tính giai thừa của 1 số tự nhiên:

int factorial1 ( int N )
  {
     if( N == 0 ) return 1;
     return N * factorial1( N-1 );
  }
int factorial2 ( int N )
  {
     int result = 1;
     for( int i = 1; i <= N; i++ )
         result *= i;
     return result;
  }

Tính số dư của N! cho M.

int ModFactorial( int N, int M )
  {
    if( N >= M ) return 0;
    int result = 1;
    for ( int i = 2; i <= N; i++ )
       {
         result *= i;
         if( result > M ) result = result % M;
       }
    return result;

  }

Tính số chữ số 0 tận cùng của N! - N! luôn chứa số thừa số 2 nhiều hơn 5 nên ta chỉ cần tìm số mũ n của 5^n trong N! là đủ. Có nhận xét sau đây :
Số c/s 0 trong N! = ( N div 5 ) * Số c/s 0 trong ( N div 5) !

int TimesOfZero( int N )
  {
     if( N == 0 ) return 0;
     N /= 5 ;
     return N + TimesOfZero( N );
  }

Trong chương trình 2 mình không chắc chắn lắm với kết quả chương trình đưa ra với những số N,M đủ lớn. Ví dụ như khi result chưa vượt quá M ( chưa thực hiện phép result = result % M ) , nhưng result * i lại vượt quá INT_MAX , mình lưỡng lự không biết có nên cho thêm điều kiện if ( result < INT_MAX / i ) hay không vì làm vậy chắc sẽ giảm thời gian thực hiện rất nhiều vì có rất nhiều vòng lặp.

[AlexF]

Trong chương trình 2 mình không chắc chắn lắm với kết quả chương trình đưa ra với những số N,M đủ lớn. Ví dụ như khi result chưa vượt quá M ( chưa thực hiện phép result = result % M ) , nhưng result * i lại vượt quá INT_MAX , mình lưỡng lự không biết có nên cho thêm điều kiện if ( result < INT_MAX / i ) hay không vì làm vậy chắc sẽ giảm thời gian thực hiện rất nhiều vì có rất nhiều vòng lặp.

int ModFactorial( int N, int M )
  {
    if( N >= M ) return 0;
    int result = 1;
    for ( int i = 2; i <= N; i++ )
       {
         result *= i;
         if( result > M ) result = result % M;
       }
    return result;

  }

áp dụng công thức (m*n)mod x= m mod x * n mod x

[aMember]

Trong trường hợp này thì m và n đều nhỏ hơn x mà. Hơn nữa cái công thức đó phải sửa lại là (m*n)mod x= ( m mod x * n mod x ) mod x ;

[QuangHoang]

Ủng hộ aMember nhé:
- Kiểm tra một số có phải là số nguyên tố không:

int primeNumber1(int n)
{
     int i,t;
     if (n<=1)return 0;
     t=sqrt(n);
     for (i=2;i<=t;i++)
          if (n%i==0)return 0;
     return 1;
}

Dựa vào lý thuyết: mọi số không phải là nguyên tố đều là bội của 2 or 3 or 5 or 7

int primeNumber2(int n)
{
     int i;
     if (n<=1)return 0;
     if (n<=3)return 1;
     if (n==5||n==7)return 1;
     if (n%2==0 || n%3==0 || n%5==0 || n%7==0)return 0;
     return 1;
}

[SmallInt]

Dựa vào lý thuyết: mọi số không phải là nguyên tố đều là bội của 2 or 3 or 5 or 7

Lý thuyết nghe lạ quá ^^.Bạn thử các số này không phải là nguyên tố nhưng đều không phải bội của các số đó : 121,169,...vv rất nhiều số miễn sao số ấy là tích của các số nguyên tố lớn hơn 7 : ví dụ : 121=11*11; 169=13*13;hoặc 143=11*13 ...còn rất nhiều

[QuangHoang]

Híc thôi chết, cái lý thuyết đó chỉ trong 120 số đầu tiên http://vi.wikipedia.org/wiki/S%E1%BB...AAn_t%E1%BB%91
Sorry mọi người T_T

[AlexF]

Trong trường hợp này thì m và n đều nhỏ hơn x mà. Hơn nữa cái công thức đó phải sửa lại là (m*n)mod x= ( m mod x * n mod x ) mod x ;

sai rồi cậu ah
chứng minh trên giấy đi,đơn giản thôi

[aMember]

Lấy ví dụ nhé 3 mod 5 = 3 ; 4 mod 5 = 4 ; theo bạn thì 3*4 mod 5 = 3 * 4 = 12 lớn hơn 5 rồi. Cái công thức đó hoàn toán chính xác.

[aMember]

Híc thôi chết, cái lý thuyết đó chỉ trong 120 số đầu tiên http://vi.wikipedia.org/wiki/S%E1%BB...AAn_t%E1%BB%91
Sorry mọi người T_T

Cái đó là sàng số nguyên tố Eratosthene, dùng để in ra các số nguyên tố nhỏ hơn n. Chắc là bạn hiểu nhầm rồi , đằng sau các số 2,3,5,7 đó chắc chắn phải có dấu 3 chấm^^. Mình lấy code về và viết lại trên C++ như sau :

#include <iostream.h>
#include <conio.h>
#include <math.h>
void main()
{
 const int N = 1000 ;
 int Prime[N+1] ;
 int i, j, k;
 Prime[1] = 0;
 k=0;
 while( k < sqrt(N) )
   {
      i = k + 1;
      while( ! Prime[i] ) i++;
      k = i;
      j = 2;
      Prime[k] = 1;
      while( k * j <= N )
        {
          Prime[k*j] = 0 ;
          j++ ;
        }
   }
 for ( i = 2; i <= N; i++ )
   if( Prime[i] ) cout << i << "  ";
 getch();

}

Đầu tiên người ta lưu các giá trị từ 2 đến n vào 1 mảng ( gọi là cái sàng ^^).
Giữ lại 2 và xoá toàn bộ các số lớn hơn 2 mà chia hết cho 2.
Đi tới phần tử tiếp theo không bị xoá ( là 3) : Giữ lại 3 và xoá toàn bộ các số lớn hơn 3 mà chia hết cho 3.
Đi tới phần tử tiếp theo không bị xoá ( là 5) : Giữ lại 5 và xoá toàn bộ các số lớn hơn 5 mà chia hết cho 5.
Cứ tiếp tục như vậy cho tới sqrt(n) ;

[developer]

Số hoàn hảo là những số có tính chất: Tổng các ước của số đó (trừ số đó) bằng chính số đó

Đây là hàm con kiểm tra một số có phải số hoàn hảo không, nếu có trả về giá trị 1, ngược lại trả về 0 :

int is_perfect_number (int n)
{
  int i,sum=0;
  for(i=1;i<n;i++)
     if(n%i==0)
         sum+=i;
  if(sum==n)
    return 1; 
  return 0;
}

Tìm ước chung lớn nhất của 2 số

Mình có mấy cách như thế này đều dùng được:

int gcd(int a, int b)
{
  if(b==0)
   return a;
  return gcd(b,a%b);
}

int gcd(int a, int b)
{
  int t;
  while(b!=0)
    t=a%b,a=b,b=t;
  return a;
}

int gcd(int a, int b)
{
  while(a!=b){
    if(a>b)
      a=a-b;
    else
      b=b-a;
  }
  return a;
}

Mình xét số dương thui nhé