Project Euler

Túm lại là cái topic này để giới thiệu về trang projectEuler, một trang vui chơi ko có thưởng, dùng để xả stress sau những giờ vui chơi vô cùng căng thẳng .. và cũng đặc biệt dành cho dân IT

http://projecteuler.net là một trang web đưa ra các bài toán (problem) thiên về thuật toán nhiều hơn là ngôn ngữ.
Các bài toán ở phần tab problem http://projecteuler.net/problems. Mỗi bài toán chỉ cần kết quả, không quan trọng bạn dùng ngôn ngữ gì (hoặc có thể ngồi nhẩm bấm máy tính cũng đc). Sau khi được giải quyết, trang web sẽ cho mọi người một thuật toán tối ưu (file pdf đính kèm ở cột bên phải, nhưng mình thấy có mỗi mấy cái đầu là có, còn về sau chẳng thấy nữa) hoặc mọi người có thể vào forum cho problem đó để xem thuật toán của các thành viên khác. Đọc mấy cái này ngộ ra nhiều thứ

Ở tab statistics>countries, mọi ng sẽ thấy danh sách member của mỗi nước (chọn mình nước nào thì trong phần account ấy). Việt Nam khá đông (dân UET cũng đông luôn ). http://projecteuler.net/country=Vietnam
Mọi người cũng nhớ để country của mình trong account là Viet Nam nha, cho anh em còn biết

Đề bằng tiếng Anh nên có một số chỗ hơi khó hiểu (cái này phải nhờ mấy bác giỏi tiếng Anh vào giúp vậy).
Mọi người cùng nhau làm cho có hứng nha. làm mấy cái này tốt cho tư duy thuật toán lắm

Mọi ng có j vào đây trao đổi nha.. Please!!!

tks chủ thớt nhá

yeah!! nhanh nào

đang làm đến problem nào rồi???

em làm trước các thím mà.. nên không tính

alo alo

có đây

Dịch hộ đề đi tớ làm với

có đề nào ko hiểu thì cứ hỏi luôn

#include <iostream>
#include <cmath>
using namespace std;
int ngto(long long int n)
{
if(n<2) return 0;
if(n==2) return 1;
long long int i=2;
while(i <= (long long int)sqrt(n) && n%i !=0) i++;
if(n%i !=0) return 1;
else return 0;
}
int main()
{
long long int a = 445642244121,kq=0;
for( long long int i=1 ; i <= a/2 ; i++)
if(a%i ==0 && ngto(i)==1)
kq =i;
cout<<kq;
system("pause");
return 0;
}

tungvuongsy đã viết:

Code:

#include <iostream>
#include <cmath>
using namespace std;
int ngto(long long int n)
{
    if(n<2) return 0;
    if(n==2) return 1;
    long long int i=2;
    while(i <= (long long int)sqrt(n) && n%i !=0) i++;
    if(n%i !=0) return 1;
    else return 0;
    }
int main()
{
    long long int  a = 445642244121,kq=0;
    for( long long int i=1 ; i <= a/2  ; i++)
    if(a%i ==0 && ngto(i)==1)
    kq =i;
    cout<<kq;
    system("pause");
    return 0;
    }

chưa xem kĩ code, nhưng phần khai báo long long thì sau giá trị cần thêm chữ "LL"
ví dụ: long long a = 600851475143LL;

12 số chạy có khác, chạy nhanh thật

Đã qua nên post code lên hưởng ứng

Code:

/*
Problem 3:
The prime factors of 13195 are 5, 7, 13 and 29.

What is the largest prime factor of the number 600851475143 ?
*/
#include <iostream>
#include <cmath>
using namespace std;
bool checkPrime(long long int temp);
int main()
{
    long long int x = 600851475143;
    long long int i = 2;
    while(i <= sqrt(x))
    {
        if(x%i != 0) i++;
        else
        {
            x = x/i;
            if(x == 1) break;
            else
                if(checkPrime(x) == true && x > i)
                {
                    i = x;
                    break;
                }
        }
    }
    cout << "The result is: " << i << "\n";
    return 1;
}
// Function checkPrime
bool checkPrime(long long int temp)
{
    int count = 0;
    if(temp < 2)
        return false;
    if(temp == 2 || temp == 3)
        return true;
    for(long long int i = 2;i <= sqrt(temp);i++)
        if(temp%i == 0)
            count++;
    if(count > 0)
        return false;
    else return true;
}

mọi người nhớ đọc cái file pdf của nó để sửa lại code cho tối ưu hơn sau khi hoàn thành nhé

Thanks Thủng nhé ^^! Thêm mỗi LL mà làm mãi không chạy được

Code:

#include<iostream>
#include<cmath>
using namespace std;
int nguyento(long long n) //kiem tra n co phai la so nguyen to hay khong
{
   int kt = 1;
   for(long long i=2 ; i<=sqrt(n) ; i++)
      if(n%i == 0)
         { kt = 0;
          break ;
          }
   return kt ;   
   
}
int main()
{
   long long a = 600851475143LL;

   for   (long long i=2 ; i<=a ; i++)
      if(a % i == 0 && nguyento(i)==1)
         cout <<i<<" ";
         
   system("pause");
   return 0;
}

Đề của problem 4 là gì vậy ? Tớ dịch không được :-(||>:

số nó to nên chạy cũng khá lâu đấy..
mà nếu lâu quá là có lỗi >:)

susu9x đã viết:

Đề của problem 4 là gì vậy ? Tớ dịch không được :-(||>:

tìm số palindromic tạo thành từ tích 2 số có 3 chữ số.
số palindromic là số mà đọc ngược đọc xuôi đều như nhau.

code linh ta linh tinh, cái đoạn checkPalindrome hơi chuối

Code:

/*
A palindromic number reads the same both ways.
The largest palindrome made from the product of
 two 2-digit numbers is 9009 = 91 × 99.

Find the largest palindrome made from
the product of two 3-digit numbers.
*/
#include <iostream>
using namespace std;
bool checkPalindrome(long temp);
int main()
{
    long result = 0;
    for(int i = 999;i > 99;i--)
        for(int j = 999;j > 99;j--)
        {
            if(checkPalindrome(i*j) == true)
            {
                if(i*j > result)
                    result = i*j;
            }
        }
    cout << "The result is: " << result << "\n";
    return 1;
}
bool checkPalindrome(long temp)
{
    if(temp%10 == temp/100000 &&
      (temp%100 - temp%10)/10 == (temp%100000-temp%10000)/10000 &&
      (temp%1000 - temp%100)/100 == (temp%10000-temp%1000)/1000)
        return true;
    return false;
}

mình thấy cái checkpalindrome hơi phụ thuộc vào số chữ số.. nếu thay bằng vòng while thì tốt hơn..

DEV.CENTER đã viết:

mình thấy cái checkpalindrome hơi phụ thuộc vào số chữ số.. nếu thay bằng vòng while thì tốt hơn..

làm vội nên chưa tính về khía cạnh tổng quát... cần chỉnh sửa nhiều... hơn nữa chắc code cũng ko tối ưu... cần xem lại phần tối ưu của nó

bác nào dịch hộ em cái đề này yêu cầu gì với >"< hàn lâm quá

Trích dẫn :

A permutation is an ordered arrangement of objects. For example, 3124 is one possible permutation of the digits 1, 2, 3 and 4. If all of the permutations are listed numerically or alphabetically, we call it lexicographic order. The lexicographic permutations of 0, 1 and 2 are:

012 021 102 120 201 210

What is the millionth lexicographic permutation of the digits 0, 1, 2, 3, 4, 5, 6, 7, 8 and 9?

bác nào dịch dùm em với

yên ắng quá