Nhờ dịch một số thuật ngữ như `square free`, `prime factors`

ddthanhdat · April 28, 2015, 6:05am

Mọi người giải thích hộ mình. Mình chưa hiểu hết nghĩa 3 câu này:

mu(1)=1, by definition;
if N is not square free, mu(N)=0;
if N is square free and contains an even number of prime factors, mu(N)=1;
if N is square free and contains an odd number of prime factors, mu(N)=-1.

Đoạn này được trích từ Problem G. Riemann vs Mertens

ltd · April 28, 2015, 6:00am

Từ link Wiki về square free

in mathematics, a square-free, or quadratfrei integer, is an integer which is divisible by no other perfect square than 1. For example, 10 is square-free but 18 is not, as 18 is divisible by 9 = 3^2.

Ta có thể hiểu, square free là số không thể chia hết cho một số chính phương nào khác 1. Ví dụ, 10 là square free nhưng 18 thì không phải, vì 18 chia hết cho 9 = 3^2. Danh sách số square free

1, 2, 3, 5, 6, 7, 10, 11, 13, 14, 15, 17, 19, 21, 22, 23, 26, 29, 30, 31, 33, 34, 35, 37, 38, 39, … (sequence A005117 in OEIS)

Nhờ ai giải thích hộ cái prime factors

laptrinhio · April 28, 2015, 6:01am

Prime Factor là thừa số nguyên tố.

ddthanhdat · April 28, 2015, 6:09am

if N is square free and contains an odd number of prime factors, mu(N)=-1.
VD: số 15=3*5 sao mu(15) ko bằng -1 mà bằng 1 vậy?

ddthanhdat · April 28, 2015, 6:13am

Đây là bài của em:
Em thiết kế gồm có: sàng ngto, factor, mang lưu trị.

#include <iostream>
#include <string.h>
#include <math.h>
using namespace std;
const long long maxn=1000000+5;
long long isPrime[maxn];
void Prime(){
	for(long long i=2;i<=maxn;i++){
		isPrime[i]=-1;
	}
	for(long long i=2;i<=maxn;i++){
		if(isPrime[i]==-1) 
			for(long long j=i;j*i<=maxn;j++){
				isPrime[j*i]=i;
			}
	}
	
}
long long factor[1000];
void recrusive_factor(long long n,long long &fn){
    if(isPrime[n]==-1){
        factor[fn]=n;
        fn++;
    }else{
        recrusive_factor(n/isPrime[n],fn);
        factor[fn]=isPrime[n];
        ++fn;
        
    }
    
}

int isfactor(long long n){
    long long fn=0;
    recrusive_factor(n,fn);
    
    for(long long i=0;i<fn-1;i++){
    	for(long long j=i+1;j<fn;j++){
    		if(factor[i]==factor[j]) return 0;
		}
	}
	return 1;
}
long long mang[maxn][2];
void m(){
	// set 1
	mang[1][0]=1;
	mang[1][1]=1;
	
	for(long long i=2;i<=maxn;i++){
		if(isPrime[i]==-1){
			mang[i][0]=-1;
			mang[i][1]=mang[i][0]+mang[i-1][1];
		}
		else{
			int m=isfactor(i);
			mang[i][0]=m;
			mang[i][1]=mang[i][0]+mang[i-1][1];
		}
	}
}

int main(){
//	cout  << daoso(3);
//	freopen("ip.txt","r",stdin);
	freopen("rs.txt","w",stdout);
	Prime();
	m();
	long long n=1;
//	while(cin>>n){
//0		if(n==0) break;
	for(long long n=20;n<=150; n++){
		cout << n <<"        " <<mang[n][0] <<"        "<< mang[n][1] << endl;
	}	
}